散列笔记

notes of hash table

概述

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。通俗的说就是将要存储的内容按照一定规则计算出一个值，并将这个值作为该内容存储在表中的位置索引。这个规则我们一般称为散列函数或者哈希函数$f(x)$。散列表可以通过散列函数直接找到内容的存储位置并进行查找，其时间复杂度为常数时间$O(1)$

常见的散列函数$^{[1]}$

直接定址法：取关键字或关键字的某个线性函数值为散列地址。即${\displaystyle hash(k)=k}$或${\displaystyle hash(k)=a\cdot k+b}$，其中${\displaystyle a\,b}$为常数（这种散列函数叫做自身函数）
平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
随机数法
除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即${\displaystyle hash(k)=k\,{\bmod {\,}}p}, {\displaystyle p\leq m}p\leq m$。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

哈希冲突

前面说了几种常用的散列函数，但是如果这个散列表需要存储的内容较多，使用散列函数求出的哈希值就有可能出现冲突，导致不同内容存到了相同的位置，这是需要避免的。处理冲突常见方法有：
开放定址法，它的基本思想是当一个位置被占用的时候，采用一种方式来寻找下一个可用的位置$^{[2]}$
线性探查(linear probing): 当一个位置被占用，找下一个可用的位置。 $h(k,i)=(h′(k)+i)$
二次探查(quadratic probing): 当一个位置被占用，以二次方作为偏移量。 $h(k,i)=(h′(k)+c_1+c_2i^2)$
双重散列(double hashing): 重新计算 hash 结果。 $h(k,i)=(h_1(k)+ih_2(k))$

链表法 ,将散列到同一个存储位置的所有元素保存在一个链表中,但这样在查找时，就需要对链表进行搜索，其时间复杂度也就不再是$O(1)$了

[1] https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
[2] https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/07_%E5%93%88%E5%B8%8C%E8%A1%A8/hashtable/