散列表
散列表（HashTable）
散列表也就是哈希表，是一种键值对（key-value pair）数据结构。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
哈希表的本质是将键（key）通过散列函数获得散列值（哈希值）映射到数组的index上，使得我们可以利用上数组可以通过index随机访问数据的特性，通过key直接访问value。
散列函数（hash）
可以看出散列函数在哈希表结构中极为重要，目标是将key尽可能均匀的映射到数组index上。
在Java的实现中，如果key是null，则hash值为0，否则获取key的hashCode，前16位与后16位进行亦或混合，解决高低位分配不均的情况，然后在计算index，使用数组长度（2的倍数）length -1 与 之前计算的混合hash进行按位于操作，获得数组index。
int index = (table.length - 1) & hash(key)
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}hash函数的设计要求有以下特性：
- hash函数计算出来的同一个key的hash值是相同的
- 得到的index不能超过数组的最大index
- 如果key1不等于key2，则hash(key1)不等于hash(key2)
在现实中，第三条很难完全做到。
散列冲突
散列冲突是两个不一样的key通过同一个hash函数得到同一个Hash值的情况，我们无法避免散列冲突。可以理解，在散列过程中我们是丢失了部分信息的。
那么我们得想办法，在出现散列冲突的时候需要如何处理？
开放寻址法
开放寻址法是解决散列冲突的的一种常用方法。
- 线性探测
它的思路是，在计算出哈希值index之后，如果这个index被占用了，那么继续向后查找空位，直到查到第一个可用空位，放进去。
查找过程也是在查找到index元素之后，该元素与目标元素比较，如果相等则表示找到，如果不相同则继续向后查找，直到第一个空位为止。
而删除过程不能查找到对应元素之后直接删除，而是需要将对应元素位置到后续第一个空位之前的所有元素向前移动一个位置。当然我们可以通过特殊标识，将已删除的位置的元素标记为已删除，在查找的时候识别到该标记的时候向后查找而不是终止查找，这样可以提高删除效率。
比如： [1,2,,,,] ，我们计算到某个元素index为0，在于是取出index为0的元素1，不为空，则无法插入，于是再检查index为1的不为空，于是再次向后检查，index为2的元素为空，则可以放进去。
- 二次探测
所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2
- 双重散列
所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
拉链法（链表法）
链表法是一种更加常用方法，它的思路是，数组中，每个位置实际上存储一个链表，所有index相同的元素挂到这个链表之上。
查找的时候，首先查找index对应的链表，然后从链表head开始，逐个节点对比查找，如果在链表上找到则找到，如果找不到则找不到。
删除也是删除对应index的链表的节点。
比如，key1和key2计算出来的index都是0，那么都会挂到index=0这个位置的链表之上。
注意
当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。装载因子是已装载元素个数与数组长度的比值。我们需要在我们的哈希表元素达到一定阈值的时候进行扩容。
散列表的装载因子=填入表中的元素个数/散列表的长度散列表实现
这里使用实现了一个简易的hashtable，使用链表法解决冲突，装载因子为0.75，也就是达到75%容量的时候需要扩容，扩容至当前容量的两倍，使用java的hashmap一样的hash函数来计算hash值。
package cn.lishiyuan.algorithm.hash;
import java.util.Arrays;
import java.util.Objects;
/**
* 拉链法哈希表
* @param <K>
* @param <V>
*/
public class HashTable<K,V> implements LeeMap<K,V> {
private int size = 0;
//
private int capacity = 1 << 4;
private double loadFactor = 0.75;
private Entry<K,V>[] table;
public HashTable() {
table = new Entry[capacity];
}
public static class Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> prev = null;
Entry<K,V> next = null;
public Entry(int hash,K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
@Override
public String toString() {
return "{" + key + ":" + value + "}";
}
}
@Override
public void put(K key, V value) {
int hash = hash(key);
int index = hash & (table.length - 1);
resizeIfNecessary();
Entry<K, V> kvEntry = new Entry<>(hash, key, value);
Entry<K,V> entry = table[index];
if (entry == null) {
table[index] = kvEntry;
size++;
return; }
while (entry != null) {
// 交换value
if (entry.hash == hash && entry.key.equals(key)) {
entry.value = value;
return; }
if (entry.next == null) {
// 已在最后一个
entry.next = kvEntry;
kvEntry.prev = entry;
size++;
return; } else {
entry = entry.next;
}
}
}
@Override
public V get(K key) {
Entry<K, V> entry = getEntry(key);
return Objects.isNull(entry) ? null : entry.getValue();
}
@Override
public void remove(K key) {
int hash = hash(key);
int index = hash & (table.length - 1);
Entry<K,V> entry = table[index];
if (entry == null) {
return;
}
while (entry != null) {
// 交换value
if (entry.hash == hash && entry.key.equals(key)) {
if (entry.prev != null) {
entry.prev.next = entry.next;
}
if (entry.next != null) {
entry.next.prev = entry.prev;
}
if(table[index] == entry){
table[index] = entry.next;
}
entry.prev = null;
entry.next = null;
size--;
return; }
entry = entry.next;
}
}
private Entry<K,V> getEntry(K key) {
int hash = hash(key);
int index = (table.length - 1) & hash;
Entry<K,V> entry = table[index];
while(entry != null){
if(hash == entry.hash && Objects.equals(entry.key,key)){
return entry;
}
entry = entry.next;
}
return null;
}
@Override
public boolean containsKey(K key) {
Entry<K, V> entry = getEntry(key);
return Objects.nonNull(entry);
}
private static int hash(Object key) {
// 对折按位与
if (Objects.isNull(key)) {
throw new IllegalArgumentException("key can not be null");
}
int h;
return (h = key.hashCode()) ^ (h >>> 16);
}
@Override
public void clear() {
Arrays.fill(table, null);
size = 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < table.length; i++) {
Entry<K, V> entry = table[i];
while (entry != null) {
sb.append(entry);
entry = entry.next;
}
}
sb.append("]");
return sb.toString();
}
private void resizeIfNecessary(){
double threshold = loadFactor * capacity;
if (size < threshold){
return;
}
// 扩容 ×2
int newCapacity = this.capacity << 1;
Entry<K,V>[] newTable = new Entry[newCapacity];
for (int i = 0; i < table.length; i++) {
Entry<K, V> entry = table[i];
if (entry == null) {
continue;
}
while (entry != null) {
int hash = entry.hash;
int index = hash & (newTable.length - 1);
Entry<K, V> kvEntry = entry;
Entry<K,V> newEntry = newTable[index];
if (newEntry == null) {
newTable[index] = kvEntry;
entry = entry.next;
continue; }
// 寻找插入位置，插入数据
while (newEntry != null){
if (newEntry.next == null) {
// 已在最后一个
newEntry.next = kvEntry;
kvEntry.prev = newEntry;
//
entry = entry.next;
break; }
newEntry = newEntry.next;
}
}
}
this.table = newTable;
this.capacity = newCapacity;
}
}
注意： 可以使用线性表1：数组与链表里面的链表来简化实现。
评论已关闭