hash表的python实现

一、hash:一般翻译散列，也称作哈希

　　任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

　hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 
也可以通俗的说hash就是找到一种数据内容和数据存放地址之间的映射关系。
      

二、hash原理：

   1.Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置，从而在想要查找该记录时，可以直接根据关键字和映射关系计算出该记录在表中的存储位置.

   2.通常情况下，这种映射关系称作为Hash函数，而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置，并不是实际的物理地址)称作为Hash地址.

   3.比如上述例子中，假如联系人信息采用Hash表存储，则当想要找到“李四”的信息时，直接根据“李四”和Hash函数计算出Hash地址即可

三、hash函数的性质

3.1 同一函数的散列值不相同，那么其原始输入也不相同，上图中k1，k3和k4。（确定性）

3.2 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是不相同的，

上图中的k2，k5这种情况称为“哈希碰撞”。（不确定性）

几种常见的哈希函数（散列函数）构造方法

• • 直接定址法 
    • 取关键字或关键字的某个线性函数值为散列地址。
    • 即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。
  • 除留余数法 
    • 取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
    • 即 H(key) = key % p, p < m。 
  • 数字分析法 
    • 当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
    • 仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。
  • 平方取中法 
    • 先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
    • 随机分布的关键字，得到的散列地址也是随机分布的。
  • 折叠法（叠加法） 
    • 将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。
    • 用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。 
  • 随机数法 
    • 选择一个随机函数，把关键字的随机函数值作为它的哈希值。
    • 通常当关键字的长度不等时用这种方法。

python实现hash：

　　存在一个长度为M的数组，key为要保存的键，h是一个哈希函数，通过%取模使得每个键映射的下标不超过M

h(key) = key % M      

　　取M = 9:

h(256) = 256 % M = 4 
h(313) = 313 % M = 7 
h(45) = 45 % M = 0 
h(421) = 421 % M = 7  #冲突
h(137) = 137 % M = 2       

insert_index_set = set()
M = 9

def h(key,M=9):
    return key % M

to_insert_key = [256, 313, 45, 421, 317]
for key in to_insert_key:
    index = h(key,M=9)
    print(index)
    first_index = index
    i = 1
    while index in insert_index_set: #检测是否已经占用
        print('\th({key} = {key} % M = {index} collision)'.format(key = key,index = index))
        index = (first_index + i * i) % M  # 根据二次方探查的公式重新计算下一个需要插入的位置
        i += 1
    else:
        print('h({key}) = {key} % M = {index}'.format(key=key, index=index))
        insert_index_set.add(index)      

 以上是一个简单的实现

下面，将实现一个完整的hashtable：  

 #一个生成阵列的类，如上图的bucket

class Array(object):
    def __init__(self,size=32,init=None):
        self._size = size
        self._items = [init] * self._size

    def __getitem__(self, index): #Array.__getitem__(index)=Array[index],获取位置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 = value

    def __iter__(self):
        for item in self._items:
            yield item

'''
定义一个 hash 表 数组的槽 
1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过，查找时只要找到 UNUSED 就不用再继续探查了 

2.使用过但是 remove 了，此时是 HashMap.EMPTY，该探查点后边的元素扔可能是有key      

3.槽正在使用 Slot 节点
'''
class Slot(object):
    def __init__(self,key,value):
        self.key,self.value = key,value


'''
Hashtable的类
'''
class HashTable(object):
    UNUSED = None
    EMPTY = Slot(None,None)

    def __init__(self):
        self._table = Array(8,init=self.UNUSED)  #[None]*8
        self.length = 0

    def _load_factor(self):
        return self.length / float(len(self._table))

    def __len__(self):
        return self.length

    #hash函数，用内置的hash函数进行哈希，然后对数组长度取模
    def _hash(self,key):
        print('abs(hash(key)): ',abs(hash(key)))
        print('len(self._table): ',len(self._table))
        return abs(hash(key)) % len(self._table)


    def _find_key(self,key):
        index = self._hash(key)
        _len = len(self._table)
        print('_find_key: self._table[index] is ',self._table[index])
        print('HashTable.EMPTY',HashTable.EMPTY)
        #[None, None, None, None, None, None, None, None]
        while self._table[index] is not HashTable.UNUSED:  #如果不是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 _slot_can_insert(self,index):
        return (self._table[index] is HashTable.UNUSED or self._table[index] is HashTable.EMPTY)

    def _find_slot_insert(self,key):
        index = self._hash(key)
        _len = len(self._table)
        while not self._slot_can_insert(index):
            index = (index * 5 + 1) % _len
        print('find_slot_insert is %s' %index)
        return index

    def __contains__(self, key):
        index = self._find_key(key)
        return index is not None

    def add(self,key,value):
        if key in self:
            print('key: %s in the hashtable' %key)
            index = self._find_key(key)
            self._table[index].value = value
            return False
        print('key: %s not in the hashtable' % key)
        index = self._find_slot_insert(key)
        self._table[index] = Slot(key,value)
        print('Slot({0},{1})'.format(key,value))
        self.length += 1
        if self._load_factor() > 0.8:
            return self._rehash()

        return True

    def _rehash(self):
        oldtable = self._table
        newsize = len(self._table) * 2
        self._table = Array(newsize,HashTable.UNUSED)
        self.length = 0

        for slot in oldtable:
            if slot is not HashTable.UNUSED or slot is not HashTable.EMPTY:
                index = self._find_slot_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.UNUSED,HashTable.EMPTY):
                yield slot.value
'''
test
'''                    

hash_table = HashTable()
hash_table.add(4,16)
print(hash_table._table._items)
print(hash_table.get(4))