HashTable 簡述，hashtable簡述

HashTable 簡述，hashtable簡述

1.解釋：使用了映射函數，把值映射到對應的位置，key－> address， address是表中的存儲位置，不是實際的地址；   2.Hash 函數設計， 分布合理，沖突少，利用率平衡，利用率高了，沖突多，利用率低了，沖突小點； (1)直接定址發： address(key) = key -2000 (2)平方取中法， 對關鍵字進行平方運算，然後取中間的幾個數字做為hash地址 address(key) =str( math.pow(key, 2) )[2, -2] (3)折疊法， 關鍵的字做一個運算 address(key) = key[0] + key[1] + key[2] (4)除留取余 知道hash表帶最大長度m， 取不大於m的質數p，對關鍵字進行取余運算 address(key) = key%p p的選取很重要，因為p選擇的好，可以最大限度降低沖突，p一般選擇小於m的最大質數   3.Hash表的大小選擇； (1)根據存儲的數量和分布來選擇； (2)動態分配，這時候需要重新計算hash地址；redis 中就有這種模式   4.沖突解決； (1)開發定址法：沖突後按照一定的策略需要尋找空位 (2)鏈地址法：鏈地址法     5.hashtable 的桶數選擇質數的原因 該段摘自http://blog.csdn.net/liuqiyao_01/article/details/14475159 設有一個哈希函數 H( c ) = c % N; 當N取一個合數時，最簡單的例子是取2^n，比如說取2^3=8,這時候 H( 11100(二進制） ) = H( 28 ) = 4 H( 10100(二進制) ) = H( 20 ）= 4 這時候c的二進制第4位（從右向左數）就”失效”了，也就是說，無論第c的4位取什麼值，都會導致H( c )的值一樣．這時候c的第四位就根本不參與H( c )的運算，這樣H( c )就無法完整地反映c的特性，增大了導致沖突的幾率． 取其他合數時，都會不同程度的導致c的某些位”失效”，從而在一些常見應用中導致沖突． 但是取質數，基本可以保證c的每一位都參與H( c )的運算，從而在常見應用中減小沖突幾率．       下面是自己實現的一個簡單的hashTable， 很多問題沒有考慮進去，也沒有編譯測試，僅作為理解 如果想看C++ STL源碼，可以參考 https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/hashtable-source.html http://blog.csdn.net/KangRoger/article/details/38640943

 
#include <stdio.h>
 
#define M 100
#define Hash_key = 29
 
template <class T>
struct HashNode
{
    T data;
    int key;
    int isNull;
    HashNode<T>* pNext;
 
    HashNode(){
        pNext = NULL;
        isNull = 1;
    }
}; 
 
 
template <class T>
class HashTable
{
private:
    HashNode<T> m_HashNodes[M];
 
    int getHashAddress(int key) {
        return key % Hash_key;
    }
 
 
public:
    HashTable(){
        // for (i=0; i<M; i++) {
        //     m_HashNodes[i].isNull = 0;    
        // }
    }
 
 
    bool insert(int key,T data) {
        int address = this.getHashAddress(key);
        if (m_HashNodes[address].isNull == 1) {
            m_HashNodes[address].data = data;
            m_HashNodes[address].isNull == 0;
        }
        else {
            // while (m_HashNodes[address].isNull == 0 && address <M) { // 線性探測法， 開發地址法
            //     address++；
            // }
            // if (address == M) {
            //     return false;
            // }
            // 
            HashNode<T>* pTmpNode = m_HashNodes[address].pNext; // 鏈地址法
            HashNode<T>* pCurNode = NULL
            while (pTmpNode != NULL) {
                pCurNode = pTmpNode;
                pTmpNode = pTmpNode->pNext;
            }
            pCurNode->pNext = new HashNode<T>();
            pCurNode->pNext->data = data;
            pCurNode->pNext->key = key;
            pCurNode->pNext->isNull = 0;
        }
    }
 
    HashNode<T> find(int key) {
        int address = this.getHashAddress(key);
        HashNode<T> node = m_HashNodes[address];
        if (node.key == key){
            return &node.data;
        }
        else {
            pCur = m_HashNodes[address].pNext;
            while (pCur != NULL){
                if (pCur->key == key) {
                    return pCur;
                }
                else {
                    pCur = pCur->pNext;
                }    
            }
            return NULL
        }
    }
 
}