HashTable 是一种非常常见且用途十分广泛的数据结构，使用 HashTable 可以大大的提高数据的检索速度，是一种非常优秀的结构。

1.Hash 算法

既然要说到 HashTable,那首先需要明白 Hash 是什么意思。Hash 的中文中翻译是“散列”，这里我感觉这个翻译还是比较奇怪的，并不能够做到让人见名知意。

Hash 是一类算法的统称，下面引用维基百科中对 Hash 函数的介绍

散列函数（或散列算法，又称哈希函数，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。

还是有点抽象？其实，Hash 函数就是对某一个复杂数据进行计算，然后得到一个不是那么复杂的数据，但是这个新的数据又能够代表它的原始数据，这就不难理解维基百科中称哈希函数创建的是数据的“指纹”了，很容易理解，现实生活中指纹是对某一个特定的人的代表，而相对于对整个人的处理，指纹的处理则简单得多。

和每个人的指纹都不同不一样，不同的数据的散列值是有可能会一样的，不同的数据产生了同样的散列值的情况称之为“碰撞”，优秀的哈希函数应该尽可能的降低产生数据碰撞的几率。

正是因为“碰撞”的存在，所以 Hash 函数是不能够从散列值计算出原值的（读者可以想一想为什么）。与此同时，散列函数必须不具有可逆性，这一特性使得 Hash 函数在密码学领域得到了极其广泛的应用。

一个典型的 Hash 算法是将整数除以一个常量并且取余法，得到的余数就是散列值，本文是用的是这种算法。

2.HashTable

当我们在对数据进行增删查操作的时候，如果数据本身很大，则会严重的降低数据的操作效率。HashTable 的核心思想是对于每一个数据，根据某种给定的 Hash 函数，计算出数据的散列值，然后根据散列值来进行查找。因为散列值在设计之初就是十分精简的，所以能够很好的提升数据的操作速度。

使用散列值来进行值的查找已经很好能够很好的提高数据的查询速度了，但这样仍然是存在问题的，问题的起因就是因为“碰撞”。由于散列函数本身的性质，导致多个不同的数据可能会有相同的散列值，此时光靠散列值肯定无法进行值的查找，一种比较典型的解决方式是通过链表这种数据结构来保存散列值相同的数据。

当进行数据插入到哈希表的时候，如果发现该数据的散列值在之前已经存在，则把散列值一样的数据做成一个链表，把最新的数据插入到该链表的尾部，而该链表本身则会把插入到“槽”中，这是一种由数组和链表组合的数据结构。

哈希表

如上图所示，左边的槽保存的是散列值，拥有同样的散列值的数据会被存放在同一个槽中，而槽的右边则是一个链表，用来把散列值相同的数据给区分并保存起来。

我们可以把 HashTable 类比为一本书，这里的散列值对应的就是书的目录，我们可以把书中具体的数据用目录的中的页码表示出来。书的目录会存在很多的章节，这里章节就对应的是 HashTable 中的槽部分，同样，书也会存在多个小节属于同一个章节的情况，所以每个槽（即章节）又可以由多个链表的节点（对应目录中的小节）组成。

3.HashTable 的 Python 实现

这里给出了 HashTable 的一种 Python 实现方式，包含了初始化（隐式的）、插入、查找、删除以及打印表结构这几个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/python
# -*- coding: utf-8 -*-

num = 10


# 一个数据节点
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next_node = None

    def set_next(self, node):
        self.next_node = node

    def get_next(self):
        return self.next_node

    def get_data(self):
        return self.data

    def data_equals(self, data):
        return self.data == data


class HashTable(object):
    def __init__(self):
        self.value = [None] * num

    def insert(self, data):
        if self.search(data):
            return True

        i = data % num
        node = Node(data)
        if self.value[i] is None:
            self.value[i] = node
            return True
        else:
            head = self.value[i]
            while head.get_next() is not None:
                head = head.get_next()
            head.set_next(node)
            return True

    def search(self, data):
        i = data % num
        if self.value[i] is None:
            return False
        else:
            head = self.value[i]
            while head and not head.data_equals(data):
                head = head.get_next()
            if head:
                return head
            else:
                return False

    def delete(self, data):
        if self.search(data):
            i = data % num
            if self.value[i].data_equals(data):
                self.value[i] = self.value[i].get_next()
            else:
                head = self.value[i]
                while not head.get_next().data_equals(data):
                    head = head.get_next()
                head.set_next(head.get_next().get_next())
            return True
        else:
            return False

    def echo(self):
        i = 0
        for head in self.value:
            print str(i) + ':\t',
            if head is None:
                print None,
            else:
                while head is not None:
                    print str(head.get_data()) + ' ->',
                    head = head.get_next()
                print None,
            print ''
            i += 1
        print ''


if __name__ == '__main__':
    hashTable = HashTable()
    hashTable.insert(10)
    hashTable.insert(11)
    hashTable.insert(1)
    hashTable.echo()
    hashTable.delete(1)
    hashTable.echo()

参考：

1.散列函数 - 维基百科，自由的百科全书
2. 一步一步写算法（之hash表）