[TOC]

散列

散列表是元素集合，其中的元素以一种便于查找的方式存储。散列表中的每个位置通常被称为槽，其中可以存储一个元素。

散列函数将散列表中的元素与其所属位置对应起来

例如：取余函数%11

将计算出的散列值插入散列表的对应位置

**载荷因子(λ)**：散列表的占用率

散列冲突：元素77在散列表的0位置，如果再来一个元素44，它的散列值也是0。将两个元素都放入同一个槽，这种情况被称作冲突，也叫“碰撞”

完美散列函数：给定一个元素集合，能将每个元素映射到不同的槽，这种散列函数称作完美散列函数。

如果元素已知，并且集合不变，那么构建完美散列函数是可能的。

不幸的是，给定任意一个元素集合，没有系统化方法来保证散列函数是完美的。

散列函数要求：冲突数最少，计算方便，元素均匀分布于散列表中。

构建完美散列函数方法：

增大散列表：使之能容纳每一个元素，这样就能保证每个元素都有属于自己的槽，元素多时候不可取

散列函数一定要高效，以免它成为存储和搜索过程的负担。如果散列函数过于复杂，计算槽编号的工作量可能比在进行顺序搜索或二分搜索时的更大，这可不是散列的初衷。

举例：字符串

# 字符串：unicode编码求和，再取余数
def hash(astring,tablesize):
    sum = 0
    for s in astring:
        sum = sum + ord(s)

    return sum%tablesize

# astr = 'cat'
# print(hash(astr, 11))

# 对异序词，这个散列函数总是得到相同的散列值
# 所以用字符位置作为权重因子
def hash(astring,tablesize):
    sum = 0
    count = 0
    for s in astring:
        count += 1
        sum = sum + ord(s) * count

    return sum%tablesize
# astr = 'cta'
# print(hash(astr, 11))

散列冲突

当两个元素被分到同一个槽中时，必须通过一种系统化方法在散列表中安置第二个元素。这个过程被称为处理冲突。

再散列泛指在发生冲突后寻找另一个槽的过程。

一种方法是在散列表中找到另一个空槽，用于放置引起冲突的元素。

简单的做法是从起初的散列值开始，顺序遍历散列表，直到找到一个空槽。注意，为了遍历散列表，可能需要往回检查第一个槽。这个过程被称为开放定址法，它尝试在散列表中寻找下一个空槽或地址。由于是逐个访问槽，因此这个做法被称作线性探测。

在这个散列表中，如果我们添加新元素44，它的散列值是0，但0已有元素77，根据线性探测，我们将把44存储在下一个None位置，也就是1中，如果再添加新元素55，则会放在2中。

当然，查找会产生额外开销，比如找55时，我们根据散列值0查到了77，值不匹配，说明可能存在散列冲突，随后进行线性搜索，1位置44，不匹配，2位置55，返回True。如果查找不存在的元素66，当我们搜索的3位置是个None时，也就是遇到空槽，就说明元素不存在，返回False。

线性探测有个缺点，那就是会使散列表中的元素出现聚集现象。也就是说，如果一个槽发生太多冲突，线性探测会填满其附近的槽，而这会影响到后续插入的元素。

扩展线性探测，不再依次顺序查找空槽，而是跳过(skip)一些槽，这样做能使引起冲突的元素分布得更均匀。“跨步”（skip）的大小要能保证表中所有的槽最终都被访问到，否则就会浪费槽资源。所以建议散列表的大小为素数

平方探测是线性探测的一个变体，它不采用固定的跨步大小，而是通过再散列函数递增散列值。如果第一个散列值是h，后续的散列值就是h+1、h+4、h+9、h+16

另一种处理冲突的方法是让每个槽有一个指向元素集合（或链表）的引用

链接法允许散列表中的同一个位置上存在多个元素。发生冲突时，元素仍然被插入其散列值对应的槽中。不过，随着同一个位置上的元素越来越多，搜索变得越来越困难。

实现映射抽象数据类型

字典是存储键-值对的数据类型。键用来查找关联的值，这个概念常常被称作映射。

python中的字典的存储结构就是由散列表实现的，这里通过映射类型进行说明。

映射抽象数据类型定义如下。它是将键和值关联起来的无序集合，其中的键是不重复的，键和值之间是一一对应的关系。映射支持以下操作。

Map()：创建一个空的映射，它返回一个空的映射集合。
put(key, val)：往映射中加入一个新的键-值对。如果键已经存在，就用新值替换旧值。
get(key)：返回key对应的值。如果key不存在，则返回None。
del：通过del map[key]这样的语句从映射中删除键-值对。
len()：返回映射中存储的键-值对的数目。
in：通过key in map这样的语句，在键存在时返回True，否则返回False。

# 映射抽象数据类型:键值对字典
class hashTalbe:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

    def hashfunction(self,key):
        return key%self.size

    def refresh(self,oldhash):
        return (oldhash+1)%self.size

    def put(self,key,data):
        hashValue = self.hashfunction(key)

        if self.slots[hashValue] is None:
            self.slots[hashValue] = key
            self.data[hashValue] = data
        else:
            if self.slots[hashValue] == key:
                self.data[hashValue] = data
            else:
                newhash = self.refresh(hashValue)
                while newhash != hashValue:
                    if self.slots[newhash] is None or self.slots[newhash] == key:
                        self.slots[newhash] = key
                        self.data[newhash] = data
                        break
                    else:
                        newhash = self.refresh(newhash)

    def get(self,key):
        hashValue = self.hashfunction(key)

        if self.slots[hashValue] == key:
            return self.data[hashValue]
        else:
            newhash = self.refresh(hashValue)
            while newhash != hashValue and self.slots[newhash] != None:
                if self.slots[newhash] == key:
                    return self.data[newhash]
                    break
                else:
                    newhash = self.refresh(newhash)
            return None

    def __getitem__(self, key):
        return self.get(key)

    def __setitem__(self, key, value):
        return self.put(key,value)

散列搜索算法

在最好情况下，散列搜索算法的时间复杂度是O(1)，即常数阶。然而，因为可能发生冲突，所以比较次数通常不会这么简单

在分析散列表的使用情况时，最重要的信息就是载荷因子λ。从概念上来说，如果λ很小，那么发生冲突的概率就很小，元素也就很有可能各就各位。如果λ很大，则意味着散列表很拥挤，发生冲突的概率也就很大。