一，哈希表

哈希表简单的理解：在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。 

哈希表基于数组的，正因为数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）

如何定位数据存储的位置呢？

h(key) = key % size

1.线性哈希表

线性哈希表可以认为就是数组，不过他对数据的存储方式不如线性表一般按顺序来，他是通过某种算法来计算得到数据下标值的。可以想象如果数据比较多，那么重下标的情况会很多，所以就有了哈希冲突。

代码实现

class Array():
    def __init__(self,size):
        self.__size = size
        self.__item = [None]*size
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value

class Slot():
    def __init__(self,key,value):
        self.key = key
        self.value = value

    def __str__(self):
        return 'key:{}  value:{}'.format(self.key,self.value)


class HashTable():
    def __init__(self):
        self.size = 4
        self.items = Array(self.size)



    def find_index_to_insert(self,key):
        index = self.get_index(key)
        if self.items[index] == None:
            return index
        else:
            while self.items[index] is not None:
                if self.items[index].key == key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return index

    def find_key(self,key):
        index = self.get_index(key)
        if self.items[index] == None:
            return None
        else:
            while self.items is not None:
                if key == self.items[index].key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return None


    def get_index(self,key):
        return hash(key) % self.size

    def put(self, key, value):
        s = Slot(key, value)
        index = self.find_index_to_insert(key)
        self.items[index] = s


    def get(self,key):
        index = self.get_index(key)
        return self.items[index]


if __name__ == '__main__':
    h = HashTable()
    h.put('name','L')
    h.put('sex','M')
    h.put('age','18')
    h.put('occupation','general')
    print(h.get('name'))
    print(h.get('sex'))
    print(h.get('age'))
    print(h.get('occupation'))

2.链式哈希表

链式哈希表可以认为是数组，不过数组内的元素是链表，有种线性表嵌套链式表的既视感，者带来的好处就多了：不仅拥有了更好的空间利用率，同时解决了哈希冲突的问题：即使出现重下标的情况，我们也可以顺着往下加，之后顺着表一个一个找就可以了。

当然对链表的处理也可以改成双向链表，不过感觉没太大必要。 

代码实现

class Array():
    def __init__(self,size):
        self.__size = size
        self.__item = [None]*size
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value

class Slot():
    def __init__(self,key,value,next=None):
        self.key = key
        self.value = value
        self.next = next

    def __str__(self):
        return 'key:{}  value:{}'.format(self.key,self.value)


class HashTable():
    def __init__(self):
        self.size = 4
        self.items = Array(self.size)


    def get_index(self,key):
        return hash(key) % self.size

    def put(self, key, value):
        s = Slot(key, value)
        index = self.get_index(key)
        if self.items[index] == None:
            self.items[index] = s
        else:
            if self.items[index].key == key:
                self.items[index].value = value
            else:
                temp = self.items[index]
                temp_next = self.items[index].next
                while temp_next is not None:
                    if temp_next.key == key:
                        temp_next.value = value
                        return
                    else:
                        temp = temp_next
                        temp_next = temp.next
                temp.next = s


    def get(self,key):
        index = self.get_index(key)
        if self.items[index]:
            if self.items[index].key == key:
                return self.items[index]
            else:
                temp_next = self.items[index].next
                while temp_next is not None:
                    if temp_next.key == key:
                        return temp_next
                    else:
                        temp_next = temp_next.next
                return None

if __name__ == '__main__':
    h = HashTable()
    h.put('name','L')
    h.put('sex','M')
    h.put('age','18')
    h.put('occupation','general')
    print(h.get('name'))
    print(h.get('sex'))
    print(h.get('age'))
    print(h.get('occupation'))

二，哈希扩容

装载因子(load factor)

如果继续往我们的哈希表里塞东西会发生什么？空间不够用。这里我们定义一个负载因子的概念(load factor)，其实很简单，就是已经使用的槽数比哈希表大小。 比如我们上边的例子插入了 8 个元素，哈希表总大小是 13， 它的 load factor 就是 $ 8/13 \approx 0.62 $。当我们继续往哈希表插入数据的时候，很快就不够用了。 通常当负载因子开始超过 0.8 的时候，就要新开辟空间并且重新进行散列了。

重哈希(Rehashing)

当负载因子超过 0.8 的时候，需要进行 rehashing 操作了。步骤就是重新开辟一块新的空间，开多大呢？感兴趣的话可以看下 cpython 的 dictobject.c 文件然后搜索 GROWTH_RATE 这个关键字，你会发现不同版本的 cpython 使用了不同的策略。python3.3 的策略是扩大为已经使用的槽数目的两倍。开辟了新空间以后，会把原来哈希表里 不为空槽的数据重新插入到新的哈希表里，插入方式和之前一样。这就是 rehashing 操作。

代码实现

class Array():
    def __init__(self,size):
        self.__size = size
        self.__item = [None]*size
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value

class Slot():
    def __init__(self,key,value):
        self.key = key
        self.value = value

    def __str__(self):
        return 'key:{}  value:{}'.format(self.key,self.value)


class HashTable():
    def __init__(self):
        self.size = 4
        self.length = 0
        self.items = Array(self.size)



    def find_index_to_insert(self,key):
        index = self.get_index(key)
        if self.items[index] == None:
            return index
        else:
            while self.items[index] is not None:
                if self.items[index].key == key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return index

    def find_key(self,key):
        index = self.get_index(key)
        if self.items[index] == None:
            return None
        else:
            while self.items is not None:
                if key == self.items[index].key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return None


    def get_index(self,key):
        return hash(key) % self.size

    def put(self, key, value):
        s = Slot(key, value)
        index = self.find_index_to_insert(key)
        self.items[index] = s
        self.length += 1
        if self.load_factor():
            self.rehashing()


    def load_factor(self):
        return self.length / float(self.size) > 0.8

    def rehashing(self):
        self.length = 0
        old = self.items
        self.size = self.size << 1
        self.items = Array(self.size)
        for s in old:
            if s:
                key = s.key
                index = self.find_index_to_insert(key)
                self.items[index] = s
                self.length += 1

    def get(self,key):
        index = self.get_index(key)
        return self.items[index]

if __name__ == '__main__':
    h = HashTable()
    h.put('name', 'L')
    h.put('sex', 'M')
    h.put('age', '18')
    h.put('occupation', 'general')
    h.put('occupation1', 'general')
    h.put('occupation2', 'general')
    h.put('occupation3', 'general')
    h.put('occupation5', 'general')
    h.put('occupation6', 'general')
    print(h.get('name'))
    print(h.get('sex'))
    print(h.get('age'))
    print(h.get('occupation'))
    print(h.get('occupation1'))
    print(h.get('occupation2'))
    print(h.get('occupation3'))
    print(h.get('occupation5'))