摘要

定义

本质

数组
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
原理:
散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是0(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组标标,从对应的数组下标的位置取数据。

散列函数

散列函数计算得到的散列值是一个非负整数;.
如果key1 = key2,那hash(key1) == hash(key2);
如果key1 != key2,那hash(key1) != hash(key2),
散列函数的设计不能太复杂,散列函数生成值要尽可能随机并且均匀分布

负载因子 load factor

衡量哈希表的 空/满 程度,一定程度上也可以体现查询的效率
负载因子 = 总键值对数 / 箱子个数
负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(可能是 1,或者 0.75 等)时,哈希表将自动扩容。

重哈希 rehash

在自动扩容时,一般会创建两倍于原来个数的箱子,因此即使 key 的哈希值不变,对箱子个数取余的结果也会发生改变,因此所有键值对的存放位置都有可能发生改变

特性

快速查找
快速插入删除
无重复可计数

哈希冲突 Hash Collision

不同的键在哈希函数作用下映射到相同的槽,即出现多对一

拉链法

Open Hashing,链表法 Chaining
每个”桶(bucket) “或者”槽(slot) “会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。
image.png

用链表延展存储

优点

  1. 处理简单,无堆积现象(即非同义词决不会发生冲突)?,平均查找长度较短
  2. 链表删除结点简单

缺点

  1. 链表内存分配会降低运行效率

    开放寻址法 Open Addressing

    Closed Hashing,开地址法
    不在本身之外开辟新空间,而是重新选择一个空闲位置

    哈希桶 Bucket Hashing

    普通哈希表满足:一个桶Bucket仅一个槽slot。
    哈希桶:一个桶Bucket多个槽slot。

    即可看做将重复部分添加每个槽后

相同映射值依次填充桶内的slot,当填满后填充值overflow内
image.png

探测 Probing

应用

作为字典dict的底层实现

  1. Java中HashMap
  2. Objective-C中的NSDictionary
  3. Redis中dict