常用数据结构之哈希表

什么是哈希表？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

记录的存储位置=f(关键字)

这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

散列函数并不是唯一的，常见的有除法、平方散列，具体可参考http://blog.csdn.net/mycomputerxiaomei/article/details/7641221

给出拉链法的一个实现：

class MyHashTable {
public:
#define HASHTABLEMAX 20
    typedef int HashDataType;
    typedef int HashPosType;
    typedef struct LinkNode {
        HashDataType data;
        struct LinkNode *next;
        LinkNode(HashDataType _data) :
                data(_data), next(NULL) {
        }
    } HashNode;
    struct HashHead {
        struct LinkNode *next;
        HashHead() :
                next(NULL) {
        }
    };

    MyHashTable() {
        initHashTable();
    }
    ~MyHashTable() {
        dropHashTable();
    }
    /*
     * 哈希表散列计算函数
     * 计算哈希表的位置
     */
    HashPosType hashFunc(HashPosType id) {
        HashPosType pos = 0;
        pos = id % HASHTABLEMAX;
        return pos;
    }
    /*
     * 初始化hash head，作为亚节点
     */
    void initHashTable() {
        for (int i = 0; i < HASHTABLEMAX; i++) {
            hashTable[i] = new HashHead();
        }
    }
    void dropHashTable() {
        HashNode *node;
        HashHead *head;
        for (int i = 0; i < HASHTABLEMAX; i++) {
            head = hashTable[i];
            node = hashTable[i]->next;
            while (node) {
                head->next = node->next;
                delete node;
                node = head->next;
            }
            delete head;
        }
    }
    /*
     * 查找当前hashTable中是否包含此元素
     */
    HashNode *find(HashDataType data) {
        HashPosType pos = hashFunc(data);
        HashNode * node = hashTable[pos]->next;
        if (node == NULL)
            return NULL;
        while (node) {
            if (node->data == data)
                return node;
            node = node->next;
        }
        return NULL;
    }
    /*
     * 插入元素
     * 去除重复元素，有重复时，直接返回false
     * 升序插入
     */
    bool insert(HashDataType data) {
        if (NULL != find(data))
            return false;
//        cout << "insert data " << data << endl;
        HashPosType pos = hashFunc(data);
        HashHead *head = hashTable[pos];
        HashNode * node = hashTable[pos]->next;
        HashNode *tem = new HashNode(data);
        //处理空
        if (node == NULL) {
            head->next = tem;
            return true;
        }
        //处理第一个有效结点
        if (node->data > tem->data) {
            tem->next = node;
            head->next = tem;
            return true;
        }
        HashNode *prev = node;
        node = node->next;
        while (node) {
            if (node->data < tem->data) {
                prev = prev->next;
                node = node->next;
            } else {
                tem->next = node;
                prev->next = tem;
                return true;
            }
        }
        prev->next = tem;
        return true;
    }
    /*
     * 删除元素
     */
    bool remove(HashDataType data) {
        HashPosType pos = hashFunc(data);
        HashHead *head = hashTable[pos];
        HashNode *prev;
        HashNode * node = hashTable[pos]->next;
        if (node->data == data) {
            head->next = node->next;
            delete node;
            return true;
        }
        prev = node;
        node = node->next;
        while (node) {
            if (node->data == data) {
                prev->next = node->next;
                delete node;
                return true;
            }
            prev = prev->next;
            node = node->next;
        }
        return false;
    }
    /*
     * 得到总元素个数
     */
    int size() {
        HashNode *node;
        int num = 0;
        for (int i = 0; i < HASHTABLEMAX; i++) {
            node = hashTable[i]->next;
            while (node) {
                num++;
                node = node->next;
            }
        }
        return num;
    }
    /*
     * 打印
     */
    void print() {
        HashNode *node;
        cout << "******************hash table**************" << endl;
        for (int i = 0; i < HASHTABLEMAX; i++) {
            node = hashTable[i]->next;
            if (node) {
                cout << "id " << i << " : ";
                while (node) {
                    cout << node->data << " -> ";
                    node = node->next;
                }
                cout << endl;
            }
        }
    }
private:
    HashHead *hashTable[HASHTABLEMAX];
public:
    static void test() {
        MyHashTable *hashTable = new MyHashTable();
        for (int i = 1; i < 5; i++) {
            hashTable->insert(i);
        }
        hashTable->print();
        hashTable->remove(3);
        hashTable->print();
        for (int i = 1; i < 5; i++) {
            hashTable->insert(i + HASHTABLEMAX * 2);
        }
        hashTable->print();
        cout << hashTable->size() << endl;
        for (int i = 1; i < 5; i++) {
            hashTable->insert(i + HASHTABLEMAX);
        }
        hashTable->print();
    }
};

参考：

http://blog.csdn.net/mycomputerxiaomei/article/details/7641221

http://blog.csdn.net/duan19920101/article/details/51579136

http://blog.csdn.net/lyflower/article/details/2540300

http://blog.csdn.net/cywosp/article/details/23397179/