[알고리즘 도론] 산목록

산열표는 일반 그룹의 확장으로 사전 조작을 지원하는 동적 집합입니다.
직접 주소 찾기 산 목록: 일반 그룹을 이용하여 직접 주소를 찾을 수 있으며, 내부 시간 내에 그룹의 임의의 위치에 접근할 수 있습니다.
링크법 산열 목록: 같은 키워드 두 개가 같은 슬롯에 비치는 것을 해결하기 위해 링크법으로 충돌을 해결합니다.그 사고방식은 같은 키워드 값의 노드를 하나의 체인 테이블로 구성하고 모든 같은 값을 체인 테이블의 끝에 꽂는 것이다.

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로 표시할 수 있다.
나눗셈 해시:
, m는 항상 2에 가깝지 않은 정수 멱의 소수를 선택하는데, 이렇게 하면 무효한 산열을 피할 수 있다.
곱셈 해시:
, 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;

}

개방 주소 찾기에서 중요한 개념은 바로'탐색'이다. 탐색은 산 목록을 따라 전진하는 길이의 크기로 선형 탐색, 2차 탐색, 이중 탐색이 될 수 있다.
선형 탐색: 실현하기 쉬우나 순서대로 군집하는 문제가 존재하고 점용조가 증가함에 따라 평균 검색 시간도 증가한다.
2차 탐색:
이중 탐색:
완전 산열: 바로 두 개의 산열을 사용하고 각 단계마다 전역 산열을 사용한다.