Java HashMap实现原理1——散列表

博主前面的文章Java HashMap实现原理0——从hashCode,equals说起有提HashMap是由散列表实现，但是没介绍，觉得只是个数据结构，清楚大概就行，直到前几天某厂的一道笔试题，让实现一个自定义的HashMap，作者蒙逼了，手撸代码犯怂。今天就带大家看下散列表的原理以及具体要求下的实现。 散列表（Hash Table，也叫哈希表），是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说，它通过把关键值映射到表中一个位置来访问记录，以加快查找的速度。哈希表的实现主要需要解决两个问题，哈希函数和冲突解决。

哈希函数

散列表内部，我们使用桶（bucket）来保存键值对，每个桶都有一个编号，编号决定了给定的键存于散列表的哪个桶中。散列表拥有的桶数被称为散列表的容量（capacity）。假设现在有编号0～M-1，共计M个桶，哈希函数的功能就是把给定的key，映射到[0,M-1]区间的某个值。对哈希函数有两个要求：计算时间短；不同的键得到的结果尽可能均匀的分布在桶号区间内。不同的Key的集合，使用不同的哈希函数才能达到效果。 设计一个较好的散列函数是不容易的，但通常我们无需设计它，可以直接采用基于概率统计的高效实现，比如Java中不少类复写了hashCode方法，该方法返回一个hashCode，该值对容量M进行取余，即可获得一个桶号。下面看几个类的hashCode()实现。

1.String类的hashCode

@Override public int hashCode() { int hash = hashCode; if (hash == 0) { if (count == 0) { return 0; } for (int i = 0; i < count; ++i) { hash = 31 * hash + charAt(i); } hashCode = hash; } return hash; }

方法内部提供了一个缓存，hashCode会记录上一次hashCode运算的结果，如果本次计算的字符串和上次一样，则直接返回上次的计算结果；否则检查字符串是否为空串，空串返回0，不是空串，则挨个取出字符串字符，反复进行“31 * hash + char“的操作。

2.Double的hashCode

@Override public int hashCode() { long v = doubleToLongBits(value); return (int) (v ^ (v >>> 32)); }

Double类的hashCode，先把double转成long，然后将它的高32位和第三十二位进行异或操作，结果作为hashCode返回。 有了hashCode之后，怎么才能得到桶号呢？刚刚说了hashCode对容量取余就可以得到桶号，但是有个问题，int型有可能为负数，所以利用hash函数对hashCode进行下转正运算

private int hash(K key) { return (key.hashCode() & 0x7fffffff) % M; }

这样得到的值就可以作为桶号，去查找值了。

冲突解决

使用不同的碰撞处理方式，会得到不同的散列表的实现。冲突解决常用的方法包括开放定址法，链地址法，建立公共溢出区等，散列表中冲突解决用的最多的是链地址法。链地址法解决冲突的实现，每个桶后面都接了一个链表，初始的时候桶为空，当放入一个元素后，该元素也作为链接的首元素，后面再有被散列到该桶的节点时，会被放入到链表的后续节点中（放入已有结点前还是后，都可以，从编程的角度，放入前面代码量少些）。在查找时，我们先找到对应的桶号，再从链表头开始依次比较是否是当前要找的元素。 除了链地址法外，开放地址法（又叫线性探测法）也较为常见。它的解决方式是创建一个M大小的数组，保存N个键值对，M>N，发生冲突时，用数组的M-N的空位解决。线性探测的过程是：发生碰撞后，检查数组的后一个位置，包含三种情况：

命中：存放着一个和待放入键相同的元素为空：位置未空，可以直接放入不命中：存放着一个键值和待放入键值不同的元素

为空则是找到了冲突解决的方案。

极简散列表

下面看个采用链地址法解决冲突的极简demo，帮助大家理解。

//链表 public class SeqSearchST<K, V> { /*结点*/ private class Node { K key; V val; Node next; public Node(K key, V val, Node next) { this.key = key; this.val = val; this.next = next; } } private Node first; //头结点 public V get(K key) { for (Node node = first; node != null; node = node.next) { if (key.equals(node.key)) { return node.val; } } return null; } public void put(K key, V val) { Node node; for (node = first; node != null; node = node.next){ if (key.equals(node.key)) { node.val = val; return; } } /*关键点2——冲突解决*/ first = new Node(key, val, first); //表中不存在相应key，则创建结点，并将其添加到链表头 } } //利用SeqSearchST实现一个散列表 public class ChainingHashMap<K, V> { private int num; //当前散列表中的键值对总数 private int capacity; //容量（桶数 ） private SeqSearchST<K, V>[] st; //链表对象数组 public ChainingHashMap(int initialCapacity) { capacity = initialCapacity; st = new SeqSearchST[capacity]; for (int i = 0; i < capacity; i++) { st[i] = new SeqSearchST<>(); } } private int hash(K key) { /*关键点1——散列函数*/ return (key.hashCode() & 0x7fffffff) % capacity; //由hashCode换算桶编号 } //由key去查找 public V get(K key) { return st[hash(key)].get(key); } public void put(K key, V value) { /*精华操作：散列函数找到位置后put，put内部包含冲突处理*/ st[hash(key)].put(key, value); } }

如上，你就可以按照基本的要求实现一个最简单的散列表了。

总结

上面只是一些最基本的操作，实际应用中，比如HashMap，还得支持动态调整数组大小等功能，不然用着用着桶满了，按上面的开放地址法解决冲突解决逻辑，就会出现死循环，所有的元素都满了且和当前待插入的元素不同，没法跳出当前循环。 本文要感谢《散列表的原理与实现》。 很惭愧，做了一点微小的贡献！