python数据结构第七天哈希表

哈希表

1、什么是哈希表：

哈希表(hash table)也叫作散列表，这种数据结构提供了键 (Key)和值(Value)的映射关系。只要给出一个Key,就可以高效查找到它所匹配的Value,时间复杂度接近于O (1) 。

2、哈希函数：

哈希函数可以简单的理解为就是小学课本上那个函数，即 ：
     

这里的f(x) 就是哈希函数,x是关键字，y是哈希值。好的哈希函数应该具备以下两个特质：
a）单射；
b）雪崩效应：输入值x的 1比特的变化，能够造成输出值y 至少一半1比特的变化；
单射很容易理解，图 a中已知哈希值 y时，键 x可能有两种情况，不是一个单射；而图 b中已知
希值y 时，键x 一定是唯一确定的，所以它是单射。由于 x和 y 一个一个地对应，这样就从本原上减少了冲突。

雪崩效应是为了让哈希值更加符合随机分布的原则，哈希表中的键分布的越随机，利用率越高，效率也越高。

3、哈希函数的实现:

在不同的语言中，哈希函数的实现方式是不一样的，在Python语言中，哈希表对应的集合 叫作字典（diet）。

下面我们以Python为例，来看看哈希函数是如何实现的。
在Python及大多数面向对象的语言中，每一个对象都有属于自己的hash值，这个hash值是
区分不同对象的重要标识。无论对象自身的类型是什么，它们的hash值都是一个整型变 量。

既然都是整型变量，想要转化成数组的下标也就不难实现了。最简单的转化方式是什么 呢？是按照数组长度进行取模运算。
index=hash(key)% size

实际上，Python中的哈希函数并没有直接釆用取模运算，而是利用了位运算的方式来优化 性能。不过在这里我们可以姑且把它简单理解成取模操作。
通过哈希函数，可以把字符串或其他类型的Key,转化成数组的下标indexo 如给出一个长度为8的数组，则当 key=ooii2i 时，
index= hash ("001121")% size=i42OO367O3%8=7
而当 key="this”时， index=hash ("this")% size=3559O7O%8=6

4、哈希表的读写操作：

有了哈希函数，就可以在哈希表中进行读写操作了。

1.写操作(put)：

写操作就是在哈希表中插入新的键值对(也被称为Entry)。

如调用dict["00293i”]=“王五”，意思是插入一组Key为002931、Value为王五的键值对。

具体该怎么做呢？

• 第1步，通过哈希函数，把Key转化成数组下标5。
• 第2步，如果数组下标5对应的位置没有元素，就把这个Entry填充到数组下标5的位置。

但是，由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获
得的下标有可能是相同的。例如，002936这个Key对应的数组下标是2； 002947这个Key 对应的数组下标也是2。

这种情况，就叫作哈希冲突。

哈希冲突是无法避免的，既然不能避免，我们就要想办法来解决。解决哈希冲突 的方法主要有两种，一种是开放寻址法，一种是链表法。

开放寻址法：

开放寻址法的原理很简单，当一个Key通过哈希函数获得对应的数组下标已被占用时，我 们可以“另谋高就”，寻找下一个空当位置。

以上面的情况为例，Entry6通过哈希函数得到下标2,该下标在数组中已经有了其他元素, 那么就向后移动1位，看看数组下标3的位置是否有空

很不巧，下标3也已经被占用，那么就再向后移动1位，看看数组下标4的位置是否有空。

幸运的是，数组下标4的位置还没有被占用，因此把Entry6存入数组下标4的位置。

这就是开放寻址法的基本思路。当然，在遇到哈希冲突时，寻址方式有很多种，并不一定 只是简单地寻找当前元素的后一个元素，这里只是举一个简单的示例而已。

链表法：

哈希表数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对 象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置 时，只需要插入对应的链表中即可。

2.读操作(get)
讲完了写操作，我们再来讲一讲读操作。读操作就是通过给定的Key,在哈希表中查找对 应的Value。

例如调用dict["oo2936”],意思是查找Key为002936的Entry在哈希表中所对应的值。

具体该怎么做呢？下面以链表法为例来讲一下。

1. 通过哈希函数，把Key转化成数组下标2。
2. 找到数组下标2所对应的元素，如果这个元素的Key是002936,那么就找到了；如 果这个Key不是002936也没关系，由于数组的每个元素都与一个链表对应，我们可以顺着 链表慢慢往下找，看看能否找到与Key相匹配的节点。
   

在上图中，首先查到的节点Entry6的Key是002947，和待查找的Keyoo2936不符。接着定 位到链表的下一个节点Entryi,发现Entryi的Keyoo2936正是我们要寻找的，所以返回 Entryi 的 Value 即可。

在众多编程语言中，有些语言的哈希表釆用了链表法，最具代表性的就是Java中的 HashMap；有些编程语言釆用的是开放寻址法，比如Python中的diet。

5、代码实现：

开放寻址法：

# -*- coding: utf-8 -*-
 
class Array(object):
 
    def __init__(self, size=32, init=None):
        self._size = size
        self._items = [init] * size
 
    def __getitem__(self, index):
        return self._items[index]
 
    def __setitem__(self, index, value):
        self._items[index] = value
 
    def __len__(self):
        return self._size
 
    def clear(self, value=None):
        for i in range(len(self._items)):
            self._items[i] = value
 
    def __iter__(self):
        for item in self._items:
            yield item
 
 
class Slot(object):
 
    def __init__(self, key, value):
        self.key, self.value = key, value
 
 
class HashTable(object):
 
    UNUSED = None  # 没被使用过
    EMPTY = Slot(None, None)  # 使用却被删除过
 
    def __init__(self):
        self._table = Array(8, init=HashTable.UNUSED)   # 保持 2*i 次方
        self.length = 0
 
    @property
    def _load_factor(self):
        # load_factor 超过 0.8 重新分配
        return self.length / float(len(self._table))
 
    def __len__(self):
        return self.length
 
    def _hash(self, key):
        return abs(hash(key)) % len(self._table)
 
 
    def _find_key(self, key):
        index = self._hash(key)
        _len = len(self._table)
        while self._table[index] is not HashTable.UNUSED:
            if self._table[index] is HashTable.EMPTY:
                index = (index*5   1) % _len
                continue
            elif self._table[index].key == key:
                return index
            else:
                index = (index*5   1) % _len
        return None
 
    def _find_slot_for_insert(self, key):
        index = self._hash(key)
        _len = len(self._table)
        while not self._slot_can_insert(index):
            index = (index*5   1) % _len
        return index
 
    def _slot_can_insert(self, index):
        return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED)
 
    def __contains__(self, key):  # in operator
        index = self._find_key(key)
        return index is not None
 
    def add(self, key, value):
        if key in self:
            index = self._find_key(key)
            self._table[index].value = value
            return False
        else:
            index = self._find_slot_for_insert(key)
            self._table[index] = Slot(key, value)
            self.length  = 1
            if self._load_factor >= 0.8:
                self._rehash()
            return True
 
    def _rehash(self):
        old_table = self._table
        newsize = len(self._table) * 2
        self._table = Array(newsize, HashTable.UNUSED)
 
        self.length = 0
 
        for slot in old_table:
            if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
                index = self._find_slot_for_insert(slot.key)
                self._table[index] = slot
                self.length  = 1
 
    def get(self, key, default=None):
        index = self._find_key(key)
        if index is None:
            return default
        else:
            return self._table[index].value
 
    def remove(self, key):
        index = self._find_key(key)
        if index is None:
            raise KeyError()
        value = self._table[index].value
        self.length -= 1
        self._table[index] = HashTable.EMPTY
        return value
 
    def __iter__(self):
        for slot in self._table:
            if slot not in (HashTable.EMPTY, HashTable.UNUSED):
                yield slot.key
 
 
def test_hash_table():
    h = HashTable()
    h.add('a', 0)
    h.add('b', 1)
    h.add('c', 2)
    assert len(h) == 3
    assert h.get('a') == 0
    assert h.get('b') == 1
    assert h.get('hehe') is None
 
    h.remove('a')
    assert h.get('a') is None
    assert sorted(list(h)) == ['b', 'c']
 
    n = 50
    for i in range(n):
        h.add(i, i)
 
    for i in range(n):
        assert h.get(i) == i
 
 
if __name__ == '__main__':
    print(
        'beg',
        test_hash_table(),
        'end',
    )

链表法：

class LinkList:
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None

    class LinkListIterable:
        def __init__(self, node):
            self.node = node

        def __next__(self):
            if self.node:
                data = self.node.data
                self.node = self.node.next
                return data
            else:
                raise StopIteration

        def __iter__(self):
            return self

    def __init__(self, iterator=None):
        self.head = None
        self.tail = None
        if iterator:
            self.extend(iterator)

    def __iter__(self):
        return self.LinkListIterable(self.head)

    def __repr__(self):
        return '<<' ",".join(map(str, self)) '>>'

    def append(self, data):
        n = self.Node(data)
        if self.head:
            self.tail.next = n
            self.tail = n
        else:
            self.head = n
            self.tail = n

    def extend(self, iterator):
        for i in iterator:
            self.append(i)

    def exist(self, n):
        for i in self:
            if n == i:
                return True
            else:
                return False


class HashTable:
    def __init__(self, size=101):
        self.size = size
        self.T = [LinkList() for i in range(size)]

    def __repr__(self):
        return ','.join((map(str, self.T)))

    def exist(self, data):
        pst = self.h(data)
        return self.T[pst].exist(data)

    def h(self, data):
        return data % self.size

    def insert(self, data):
        pst = self.h(data)
        if self.exist(data):
            return 'Insert Duplicated'
        else:
            self.T[pst].append(data)

这篇好文章是转载于：学新通技术网