本文共 579 字，大约阅读时间需要 1 分钟。

是什么

散列表是数组的一种扩展，利用的是数组的随机访问特性。散列表的核心是散列函数，散列函数有三个要求：1. 散列函数得到的值是一个非负整数; 2. 如果key1=key2,那么hash(key1)==hash(key2);3. 如果key1!=key2，那hash(key1)!=hash(key2),这种情况几乎不可能存在

散列冲突

1. 开放寻址法
   线性探测、二次探测、双重散列
   数据量小，装载因子小的是啥时候适合
2. 链表法
   适合存储大对象、大数据量的散列表。
   数组+链表

散列函数

• 设计简单，很多计算消耗性能
• 散列函数的生成值尽可能的随机并且均匀分布
  有数据分析法、取余、直接寻址、平方取中、折叠、随机数

扩容

当装载因子过大的时候，冲突的可能性越大，这个时候就需要动态扩容了，动态扩容可以通过将扩容操作穿插在查找和插入操作中，实现高效的扩容。

工业级散列表

1. 初始大小可调整
2. 根据装载因子动态扩容
3. 通过红黑树解决散列冲突问题
4. 散列函数简单，分布均匀

散列表应用

LRU缓存淘汰算法

缓存有添加、删除、查找三个操作，底层本质都需要查找操作，通过散列表和链表结合，可以使时间复杂度降到O(1)。

Redis有序集合

根据用户ID查找信息的时候，构建散列表来实现

JAVA LinkedHashMap

按照访问时间排序，基本上可以看做是一个LRU缓存淘汰的缓存系统

转载地址：http://plbjn.baihongyu.com/