- 散列表：
- 也叫做哈希表，这种数据结构提供了键Key和值Value的映射关系
- 只要给出一个Key，就可以高效查找到他所匹配的Value
- 时间复杂度接近于O(1)
- 哈希函数
- 通过哈希函数把Key和数组下标进行转换
- 在java及大多数面向对象的语言中，每一个对象都有属于自己的hashcode，这个hashcode是区分不同对象的重要标识，无论对象自身类型是什么，他们的hashcode都是一个整型变量
- 按照数组长度进行取模运算：index = HashCode(Key) % Array.length
- 通过hash函数，可以把字符串或其他类型的Key，转化成数组的下标index：
- 如给出一个长度为8的数组，则当key = 001121时，index = HashCode(“001121”) % Array.length = 1420036703 % 8 = 7
- 当key=this时，index = HashCode(“this”)%Array.length = 3559070%8 = 6
- 读写操作
- 写操作put：
- 写操作就是在散列表中插入新的键值对
- 如调用hashMap.put(“002931”,“lpy”);意思是插入一组key为002931，value为lpy的键值对
- 通过哈希函数，把Key转化为数组下标5
- 如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5的位置
- 但是由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的，例如002936这个Key对应的数组下标是2,002947这个key对应数组下标也是2，这种情况叫做哈希冲突
- 解决哈希冲突：一种是开放寻址法，一种是链表法
- 开放寻址法：
- 当一个Key通过哈希函数获得对应的数组下标已被占用时，那么就寻找下一个空挡位置
- 例如:Entry6通过哈希函数得到下标2，改下标在数组中已经有了其他元素，那么就向后移动1位，看看数组下标3的位置是否有空，如果下标3的也已经被占用，那么就再向后移动1位，看看数组下标4的位置是否有空，如果数组下标4的位置还没有被占用，就把Entry6存入数组下标4的位置
- 在java中，ThreadLocal所使用的就是开放寻址法
- 开放寻址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记，直到有下个元素插入才能真正删除该元素
- 链表法：
- HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点，每一个Entry对象通过next指针指向他的下一个Entry节点，当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可
- 读操作get
- 读操作就是通过给定的Key在散列表中查找对应的value
- 例如调用hashMap.get(“002936”)，意思是查找key为002936的Entry在散列表中所对应的值
- 通过哈希函数，把key转化为数组下标2
- 找到数组下标2所对应的元素，如果这个元素的key是002936，那么就找到了，如果这个key不是002936也没关系，由于数组的每个元素都与一个链表对应，可以顺着链表往下找，看看能否找到与Key相匹配的节点
- 扩容
- 当经过多次元素插入，散列表达到一定饱和度时，key映射位置发生冲突的概率会逐渐提高，这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响
- 这时，散列表就需要扩展他的长度，也就是进行扩容
- 影响扩容因素有两个
- capacity：即hashmap的当前长度
- LoadFactor：即hashMap的负载因子，默认值为0.75f
- 衡量HashMap需要进行扩容的条件为：HashMap.Size >= Capacity * LoadFactor
- 扩容的步骤
- 扩容，创建一个新的Entry空数组，长度是原数组的2倍
- 重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中，因为长度扩大以后，hash的规则也随之改变，所以需要重新Hash
- 当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树
