Skip to content

Latest commit

 

History

History
109 lines (76 loc) · 6.78 KB

散列表.md

File metadata and controls

109 lines (76 loc) · 6.78 KB
Raw

散列表

定义

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

散列函数

特点

  1. 确定性 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。

  2. 散列碰撞（collision） 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。

  3. 不可逆性 一个哈希值对应无数个明文，理论上你并不知道哪个是。

  4. 混淆特性 输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

如何设计一个散列函数? 散列函数设计的三个基本要求:

  1. 散列函数计算得到的散列值是一个非负整数(数组下标是从0开始的);
  2. 如果key1 = key2，那hash(key1) == hash(key2);
  3. 如果key1 ≠ key2，那hash(key1) ≠ hash(key2)。

散列函数的设计并不复杂，追求的是简单高效、分布均匀。

散列冲突

对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的散列冲突。 即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。

常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。 那么如何重新探测新的位置呢?

  • 线性探测(Linear Probing)
  • 二次探测方法
    • 使用二次探测进行探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列为 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。
  • 双重散列方法
    • 使用一组散列函数 hash1(key)，hash2(key)，hash3(key)...如果计算得到的存储位置已经被占用，再用下一个散列函数，依次类推，直到找到空闲的存储位置。

装载因子

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证 散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。

装载因子的计算公式是:

散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

优点:

  • 开放寻址法不像链表法，需要拉很多链表。
  • 散列表中的数据都存储在数组中，可以有效地利用CPU缓存加快查询速度。
  • 序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。

缺点:

  • 删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。
  • 在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。
  • 装载因子的上限不能太大, 所以更浪费内存空间。

链表法

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。在散列表中，每个“桶(bucket)”或者“槽(slot)”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

插入的时间复杂度是O(1);查询和删除的时间复杂度是O(n);

优点:

  • 对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。实际上，这一点也是我们前面讲过的链表优于数组的地方。
  • 对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。

缺点:

链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链 表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这方面对于执行效率也有一定的影响。

总结:

  • 数据量比较小、装载因子小的时候，适合采用开放寻址法
  • 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用跳表, 红黑树代替链表。

附: 何为一个工业级的散列表?工业级的散列表应该具有哪些特性?

  • 支持快速的查询、插入、删除操作;
  • 内存占用合理，不能浪费过多的内存空间;
  • 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

如何实现这样一个散列表呢?

  • 设计一个合适的散列函数;
  • 定义装载因子阈值，并且设计动态扩容策略;
  • 选择合适的散列冲突解决方法。

为什么散列表和链表经常一块使用?

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说，它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历。 因为散列表是动态数据结构，不停地有数据的插入、删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低。为了解决这个问题，我们将散列表和链表(或者跳表)结合在一起使用。

关键知识点: 散列函数、装载因子、动态扩容策略，散列冲突的解决办法。

YYMemoryCache 缓存内部用双向链表和 NSDictionary 实现了 LRU 淘汰算法，使用pthread_mutex来保证线程安全;