【算法导论】散列表

时间：2014-03-12 16:01:07 阅读：344 评论：0 收藏：0 [点我收藏+]

散列表是普通数组的扩展，它是一种支持字典操作的动态集合。

直接寻址散列表：利用普通数组可以直接寻址，使得能在 $O(1)$ 内时间内访问数组中的任意位置。

链接法散列表：为了解决两个相同的关键字映射到相同的一个槽中，用链接法解决这个冲突。其思路就是将相同关键字值的节点组成一个链表，每个相同的值插到链表的结尾处。

template<class _key>
class cHashTable
{
public:
    cHashTable(int slotNum=0, int (*hashFunction)(_key)){
        this.slotNum=slotNum;
        this.hashFunction=hashFunction;

        hashTableChain=new List<_key>*[slotNum];
        for (int i = 0; i < slotNum; ++i)
        {
            hashTableChain[i]=NULL;
            /* code */
        }
    };
    ~cHashTable(){
        delete[] hashFunction;
        delete[] hashTableChain;
    };

    /* data */
private:
    int slotNum;
    int (*hashFunction)(_key);
    List** hashTableChain;
public:
    void chainedHashInsert(_key x);
    Node<_key>* chainedHashSearch(_key x);
    bool chainedHashDelete(_key x);
};


void cHashTable::chainedHashInsert(_key x){
    int key=hashFunction(x);
    if(hashTableChain[key]!=NULL){
        Node* cur=hashTableChain[key]->next;
        while(cur!=NULL){
            cur=cur->next;
        }
        Node* newNode=new Node(x);
        hashTableChain[key]=new List<_key>*();
        hashTableChain[key].insert(newNode);
    }
    else{
        Node* newNode=new Node(x);
        hashTableChain[key].insert(newNode);
    }
}

bool cHashTable::chainedHashDelete(_key x){
    int key=hashFunction(x);
    if(hashTableChain[key]==NULL){
        return false;
    }else{
        Node* dNode=hashTableChain[key].search(x);
        hashTableChain[key].delete(dNode);
    }
}

Node<_key>* cHashTable::chainedHashSearch(Node* x){
    int key=hashFunction(x->value);
    if(hashTableChain[key]==NULL){
        return NULL;
    }else{
        Node* searchResult=hashTableChain[key].search(x->value);
        return searchResult;
    }
}

散列函数：好的散列函数可以将关键字尽可能的散列到插槽位置中的任一个，并与其它关键字散列到哪个插槽无关。比如可以将关键字转换成自然数，在ASCII字符集中，p=112,t=116,如果以128为基数，那么字符串p就可以表示为112*128+116.

除法散列法：

$h(k)=k mod m$ ,m常常选择一个不太接近2的整数幂的素数，这样可以避免无效的散列。

乘法散列法：

$h(k)=[m(kA mod 1)]$ ,m可以选择2的某个幂次，k为某个小数。

全域散列法：是为了避免恶意的操作使得关键字全部散列到同一个槽中发生，采取随机地选择散列函数，使之独立于关键字的方法。全域散列是随机地选择一个hash函数，该hash函数被选择之后，对于本次应用的所有操作，hash函数都将都将不再改变。

开放寻址法

template <typename K>
class cOpenAdressHash
{
public:
    cOpenAdressHash(int hashSize, int(* hashFunction)(K x,int i)){
        this.hashSize=hashSize;
        this.hashFunction=hashFunction;
        hashData=new int(hashSize);
    };
    ~cOpenAdressHash(){
        delete[] hashFunction;
    };
public:
    bool hashInsert(K x);
    int hashSearch(K x);
    bool hashDelete(int index);
    /* data */
private:
    int hashSize;
    int (* hashFunction)(K x,int i);
    K* hashData;
    K  hasDeleted;
};

template <typename K> bool cOpenAdressHash::hashInsert(k x){
    int i=0;
    int key=hashFunction(x,i);
    while(i<hashSize&&hashData[key]==NULL&&hashData[key]!=hasDeleted){
        i=i+1;
        key=hashFunction(x,i);
    }
    if(i<hashSize){
        hashSize&&hashData[key]=x;
        return true;
    }
    else
        return false;
}

template<typename K> hashSearch(K x){
    int i=0;
    int key=hashFunction(x,i);
    while(i<hashSize&&hashData[key]!=x){
        i=i+1;
        key=hashFunction(x,i);
    }
    if(i<hashSize){
        return key;
    }
    else
        return false;
}
template <typename K>hashDelete(int index){
    if(index<0||index>hashSize)
        return false;
    if(hashData[index]==NULL||hashData[index]==hasDeleted)
        return false;
    hasDeleted[index]=hasDeleted;
}