【深入Java基础】HashMap总结

HashMap总结

hashmap的基于数组和链表及红黑树实现的哈希表。采用数组作为键值对的容器，数组中存放的是单链表的头节点。hashmap采用链表的方式(链地址法)处理hash冲突，当发生冲突时，将冲突的元素链接到链表上去。hashmap的key和value都支持null值，而hashtable则不支持。它不是同步的，但是可以通过适当的方法变为支持同步的。

HashMap的存储结构

HashMap采用数组+链表的结构实现entry的存储。在1.8之后会根据一定的阈值将链表转化为红黑树，以提高效率。

这是hashmap的存储结构：

HashMap的存储过程

put操作，在前面的源码分析中我们了解到，put的时候是先计算hash数组的下标，判断当前位置有没有entry，如果没有（无冲突）则直接将entry放到该下标处，如果有（发生冲突），则通过链表或者红黑树解决冲突。

 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

注意:

其实每一个Entry都是一个单链表的Node，里边有next“指针”，指向下一个Node。 put操作的流程如下：

注意:

这里判断key是否存在是这样写的

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

事实上通过(k = p.key) == key || (key != null && key.equals(k)这一句就可以判断key是否相同了，为什么还要p.hash==hash呢？

因为如果hash不同，则key必然不同；hash相同key可能相同，所以通过这句话就可以直接过滤掉key不相同的，不用再进行equals比较，因为equals是比较费时的，这么做是为了提高效率。

问题：hashcode相等的一定是同一个对象嘛，它们的equals为true嘛？

回答：不一定，因为hashcode的计算方法不同，相同的hashcode不一定是同一个对象。同一个对象的hashcode一定相等，它们的equals一定为true，反过来则不成立。

haspmap的取值过程

get操作和put操作基本类似，只不过一个是取一个是存。通过之前文章的源码分析我们可以知道，在取值的过程中先判断hash数组table是否为空，不为空，则通过hash值计算索引判断要获取的是否是hash数组里的节点（就是头节点），如果是，则返回，如果不是则遍历链表（或者红黑树）直到找到该节点。

hashmap的删除过程

删除和存取十分类似，不再赘述。

hashmap的同步

hashmap不是同步的，不能直接用于多线程中。我们可以手动的在put、remove和replace等可能引起modCount改变的操作上加上synchronized来同步（或者采用加锁的方式）。

或者使用Collections.synchronizedMap(map)来获取一个同步的map。

哈希冲突的解决方法

1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

2.再哈希法

3.链地址法(比如hashmap)

4.建立一个公共溢出区