Java HashMap工作原理及实现

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。

hash函数的实现
通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

put 函数的实现 思路
1，对key 的hashCode（）做hash 然后再计算index
2，如果没用碰撞直接放到bucket
3，如果碰撞了 ，以链表的形式存在buckets
4，如果碰撞导致链表过长 就把链表转换成红黑树
5，如果节点已经存在就替换old value（保证key 的唯一性）
6， 如果bucket 满了 （超过load factory * current capacity） 就resize

get 函数的实现
1，bucket 里的第一个节点 直接命中
2，如果有冲突 ，则通过key.equals(k) 去查找对应的entry
若为树 则在树种通过 key.equals(k) o(logn)
若为链表 ，则在链表中通过 key.equals(k) 查找 ，o(n)

hash的实现
在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。