(2019.11.28)HashMap原理总结

HashMap原理总结

首先我们要了解什么是哈希算法。

1、什么是哈希?

哈希算法,就是把任意长度值(key),通过散列算法变换成固定长度的地址,然后通过这个地址访问的数据结构。这个散列算法就叫做哈希函数,存放数据的数组叫做哈希表。(这让我联想到大学里计算机组成原理中内存的命中算法类似)

(2019.11.28)HashMap原理总结

2、HashMap在jdk1.7中使用数组加链表的结构存储数据,jdk1.8中将原先的链表改成了二叉树(当链表的长度超过8时,由原先的链表转换成二叉树)

(2019.11.28)HashMap原理总结

3、采用数组加链表的数据结构,首先你能够根据下标立马找到该元素,然后在小范围内遍历链表直到找到key和value都相等的元素。

4、当我们链表边长了之后,我们遍历链表的效率会降低,这个时候采用二叉树的结构能够有效的降低查找的复杂度。

(2019.11.28)HashMap原理总结

 

HashMap数据结构为数组+链表;

jdk8对HashMap的优化使其结构变成了数组+链表+二叉树;

HashMap和HashTable,ConcurrentHashMap主要是线程安全,前者非线程安全;

HashTable和ConcurrentHashMap都是线程安全,但是实现方式不一样,前者通过关键字synchronized实现,后者通过加锁的形式实现;