一:什么叫做散列表 (哈希表)
散列表是存储key、value映射的一种集合。散列表也叫做哈希表
散列表底层也是数组,只是通过一种hash函数来计算他的key值
二:hash函数
在Java中每一个对象都有属于自己的hashcode,这个hashcode是区分不同对象的重要标识。无论对象自身类型是什么,它们的hashcode都是一个整新变量。
计算hash函数(取模运算)
index=Hashcode(Key)%Array.length
在java中hash函数并没有直接采用取模运算,而是利用了位运算的方式来优化性能。
三:hash冲突
hash冲突是指在我们的散列表中,有两个不同对象他们的hash值是一样的。导致他们的key指不一样,计算出来的下标一样。
解决方法一:开放寻址法
当查找出来的下标被占用时,我们就 另谋高就 ,寻找下一个空挡位置
(ThreadLocal使用的就是开放寻址法)
解决方案二:链表法
在散列表中,每一个元素不仅是一个entry对象,还是每一个链表的头节点,每一个entry对象通过next指针指向它的下一个entry节点。当一个新的entry对象发生hash冲突时,就把该对象放入链表next中即可。
四:hashmap的读取操作
哈希表是由数组+链表组成的,数组的默认长度为16(可以自动变长。在构造HashMap的时候也可以指定一个长度),数组里每个元素存储的是一个链表的头结点。而组成链表的结点其实就是hashmap内部定义的一个类:Entity。
Entity包含三个元素:key,value和指向下一个Entity的next
我们通过元素的key计算它的hash值,拿到它的下标,查看对应的下标存储的key值对不对应。不对应就顺着链表的next一直往下找,直到找到尾节点或者找到相同匹配的key。
五:hashmap的扩容操作
hashmap有链表为什么要进行扩容呢?
当我们的散列表达到一定的饱和度时,key映射位置发生冲突的概率逐渐提高,这样一来,大量元素都会拥挤在相同数组下标位置,形成很长的链表。而我们链表查询是比数组慢的,时间复杂度是O(n)。
hashmap扩容方法?
hashmap的扩容因子是0.75,就是达到容量的百分之75就会进行扩容。
(为什么扩容因子是0.75,因为数组容量越大,发生hash碰撞的概率也就越小,当数组满了之后,hash碰撞的概率会变得更高。)
1:扩容,创建一个新的entry空数组,长度是原来的两倍。
2:重新hash,遍历原来的Entry数组,把所有的Entry重新hash到新数组中。为什么要重新hash呢?
因为我们数组长度扩容后,我们hash函数也会进行改变,数组原来的key计算的hash值获取的下标也会进行改变。这样hashmap的hash冲突概率会减少,链表长度也会减少。查询插入速度也会更快。