CS161 Lecture 3 数据结构-Hash Table

CS161

有些问题是排序所不适合的，比如需要求解一个列表中最常出现的元素。用排序也是可以解决的，即排序后挨个数连续索引中相同的元素数。但是这类问题是有更好的解决办法的。即Hash Table，散列表。

Hash Table

定义

Hash Table类似于一个列表，每一个key对应一个value。key根据某个方程转换成一个整数索引（index），然后列表的这个索引的位置存储这个value。所以一个Hash Table具有两个组成部分：

1. (A) 类似列表的存储结构。每个元素是(key, value)。这个列表要足够大到储存所有的输入还要有多余的空间。一般最好的情况是保持2/3满，如果太满的时候要把列表的长度提高到双倍并且重新分配之前的元素，重新构建。
2. (h) Hash Function用于映射key值到index，映射区间0~length-1。

在Python中dictionary是由Hash Table实现的。A[h(key)]=(key, value).

“列表最多出现的元素”问题优化解决方法

伪代码

count={}
for x in input:
    if x in count:
        count[x] += 1
    else: 
        count[x] = 1
howmany, mode = max((count[x], x) for x in count)
return mode

复杂度分析

假定dictionary使用的散列表，所以每一次运算只需要O(1)复杂度。在构建Dictionary时循环了n次，即为O(n)。寻找max的过程又是O(n)，总体复杂度即为O(n) + O(n) = O(n)。

Hash Table with Linear Probing

当散列表插入元素时，两个不同的key映射到同一个index的情况称作Collision（冲突），Linear Probing（线性探测）是常见的解决Collision问题的办法。当一个元素插入时，如位置已经被占，从此位置开始向后探测，直到遇到一个空位置，插入此元素。因为这个index的不确定性，get(k)和set(k)要对应着写。

get(k)

def get(k):
    i = h(k)
    while A[i] occupied by a different key:
    # length of the loop = # of cells skipped
        i = (i + 1) mod t(size of the hash table)
    return value stored in A[i] # 如果key=k了循环跳出就会走到这步
                or if A[i] is empty then raise indexError: key not found

set(k)

def set(k):
    i = h(k)
    while A[i] occupied by a different key:
        i = (i + 1) mod t
    # 不occupy了，即在空的时候就会跳出
    A[i] = (k, v)

删除元素

删除元素是可能的，但是不可以直接清空一个位置，因为清空后会打乱本来的顺序，可能会打断本来的一个linear probing的key而导致那个key无法被接触。删除的时候要把后面的元素前移补上此空位。

为分析复杂度而提出的假设

load factor ($\alpha$)

定义是$\frac{n}{t}$，n是此hash table被占的位置数量，t是整个array的长度。$\alpha<1$

随机函数 h

几率同等地返回一个数字的映射值。

复杂度分析

一个随机函数的运算时间是此函数的所有可能性*各自可能性的时间。对线性探测的分析，使用“在当前位置开始连续l格后是目标”的可能性。最后可得出常数级运算复杂度O(1)。