由于最新SDK里面的HashMap发生hash碰撞的时候，用的是新的算法二叉树去实现，二叉树本人不熟，所以这里分析的是老的HashMap的实现
前言
想到HashMap，是一个用于对数据做存入和取出的操作的数据结构，但是为什么速度会快，快在哪里，对于一个元素的插入，在不超出容量的情况下，数组(List)插入最坏的时间复杂度是O(N),查找的时间复杂度为O（1），而对于链表（单链表），插入由于不需要移动数组元素，所以时间复杂度为O（1），而查找需要遍历，所以是O（n）,在这种情况下，HashMap,正是结合了数组跟链表的有点实现的。
看插入的方法 ：
通过上面的secondaryHash方法，得到一个hash码，然后为了防止溢出，跟数组的最大下标进行与操作，与就是保留最低位，
然后会判断当前tab[index]是否为空，是的话，直接添加一个Entry进去tab[index]，
如何当前要插入的元素的key值对应的index在tab里面是不为空的时候，这个时候就是发生哈希碰撞。
1.判断当前要插入的元素的hash码跟插入的key是否跟当前发生碰撞的tab[index]的对应hash和可以是否相同，相同就说明当前是同一个数据，替换老的数据就行
2.这个时候就要在当前发生碰撞的tab[index]，开辟一个链表存储当前的要插入的数据：
来看HashMapEntry的实现：
从上面的数据结构可以知道HashMapEntry是一个单项链表，所以放生碰撞的时候，会把碰撞的tab[index]放在新加入的entry的下一个节点。
所以put方法里面可以知道，HahsMap其实就是数组+链表的结合体。由于数组的下标是散列标，所以在一般情况下，是不需要跟顺序数组一样在某个位置插入的时候要向后移动数组后面的元素.
HashMap将hash直接映射到数组，时间复杂度o(1)。所以这样取出也是一样：
拿数据的时候，如果刚好拿到的的hash对应是之前插入发生碰撞的一项，由于碰撞的时候，会在对顶的tab[index]生成一个单项链表，所以这个时候就是单项链表查询数据。
通过上面的key.hashCode和key.equal方法，就知道了使用HashMap进行存储的时候，key为什么要重写hashCode和equal方法了。
如何不重写，当发生碰撞的时候，去拿数据的时候，会找不到对应的key而拿到null。
补充HashMap的扩容：
```
/**
* Doubles the capacity of the hash table. Existing entries are placed in
* the correct bucket on the enlarged table. If the current capacity is,
* MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
* will be new unless we were already at MAXIMUM_CAPACITY.
*/
private HashMapEntry[] doubleCapacity() {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity *2;
HashMapEntry[] newTable = makeTable(newCapacity);
if (size ==0) {
return newTable;
}
for (int j =0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry e = oldTable[j];
if (e ==null) {
continue;
}
int highBit = e.hash & oldCapacity;//每次去跟容量与是为了防止下标越界
HashMapEntry broken =null;
//将旧的数据从oldCapacity大小的下标开始递增放入新的table里面
newTable[j | highBit] = e;
for (HashMapEntry n = e.next; n !=null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
//hashmap里面元素有可能发生碰撞后，存在一个单链表里面
//同样将链表的数据拷到新的table
if (nextHighBit != highBit) {
if (broken ==null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken !=null)
broken.next =null;
}
return newTable;
}
private HashMapEntry[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry[] newTable
= (HashMapEntry[])new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >>1) + (newCapacity >>2);// 3/4 capacity
return newTable;
}
```
网友评论