散列表用的是数组支持按照下标随机访问数据结构的特性，所以散列表其实就是数组的一种扩展，由数组烟花而来，可以说，没有数组，就没有散列表
散列函数
如何构造散列函数
1，散列函数计算得到的散列值是一个非负值
2，如果key1=key2，那hash(key1)=hash(key2)
2，如果key1≠key2，那hash(key1)≠hash(key2)
散列冲突
如何解决散列冲突
1，开放寻址法（线性探测法、二次探测，双重散列）
缺点
解决冲突，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。所以装填因子上限不能太大
当数据量比较小，装填因子小的时候适合使用开放寻址法，java中ThreadLocalMap使用的就是开放寻址
2，链表法
存储大地偶像，大数据量的散列表，而且比起开放寻址法，他更靓货，支持更多优化策略，比如红黑树代替链表
装载因子
散列表的装载因子=填入表中元素个数/散列表长度
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降
一般装载因子大于0.7就需要散列表扩容
均摊法分批次扩容
一个高效的LRU算法
散列表+双向链表
LRU算法需要解决的问题
查找一个元素
删除一个元素
添加一个元素
网友评论