해시 테이블을 검색하려면 어떻게해야합니까?

Question

난 해시 테이블에 대해 배우기 시작했는데 삽입하는 법은 알고 있지만 검색 방법은 이해하지 못했다. 키

int Hash (int key) { 
    return key % 10; //table has a max size of 10 
} 

선형 충돌 해결을 위해 프로빙 해싱

:이 내가 떨어져이 질문을 내놓고됩니다 알고리즘이다.

1, 11 및 21 키를 사용하여 삽입을 두 번 호출한다고 가정합니다. 이렇게하면 3 개의 키 모두에 대해 슬롯 1이 반환됩니다. 충돌 해결 후 테이블은 슬롯 1, 2 및 3에 1, 11 및 21 값을 갖게됩니다. 이것은 삽입에 대한 나의 이해와 함께 일어날 것이라고 가정합니다.

키 11과 21을 검색하면 어떻게 슬롯 2와 3을 얻을 수 있습니까? 내가 읽었던 해쉬 테이블 검색은 원하는 슬롯에 도착할 때를 제외하고는 삽입하는 것과 똑같은 것을해야한다. 그 슬롯에 값을 넣는 대신에 그 값을 반환한다.

글자 그대로 받아 들여 동일한 알고리즘을 적용하면 키 11을 검색하면 슬롯 1에서 시작하여 빈 슬롯을 찾을 때까지 계속 탐색하므로 앞으로 슬롯 4에 도착합니다. 비록 그것이 비어 있지 않기 때문에 그것은 내가 원하는 것 일지라도 그것은 슬롯 2에서 멈추지 않을 것입니다.

별도의 체인을 사용하더라도이 문제로 어려움을 겪고 있습니다. 3 개의 키는 모두 슬롯 1에 저장되지만 동일한 알고리즘을 사용하여 검색하면 링크 된 목록의 노드가 아닌 슬롯 1을 반환합니다.

Answer 1

각 슬롯에는 키/값 쌍이 저장됩니다. 각 슬롯을 검색하면서 키가 검색중인 키와 같은지 확인하십시오. 검색을 중지하고 동일한 키를 찾으면 값을 반환합니다.

별도의 연결을 사용하면 목록에서 각 키에 대해 키를 확인하면서 선형 검색을 수행 할 수 있습니다.

Answer 2

보통 테이블의 각 항목을 구조체로 만들어 충돌을 처리 할 수있는 연결된 목록을 만들 수 있습니다. 이것은 충돌을 상당히 줄입니다. 이 같은.

struct hashtable 
{ 
    int key; 
    struct hashtable *pList; 
}; 

struct hashtable ht[10]; 

void Insert(int key); 
{ 
    index = Hash(key); 
    if (!ht[index].key) 
    { 
     ht[index].key = key; 
     ht[idnex].pList = 0; 
    } 
    else 
    { 
     struct hashtable *pht; 
     pht = ht[index].pList; 
     while (pht->pList) 
      pht = pht->pList; 
     pht->pList = new struct hashtable; 
     pht->pList->key = key; 
     pht->pList->pList = 0; 
    } 
    return; 
} 

룩업 기능은 물론, 그것은 첫 번째 항목의 키 일치를 찾을 수없는 경우 목록을 통과해야합니다. 성능이 중요한 경우 링크 된 목록을 정렬하고 이진 검색을 사용하는 등의 다른 전략을 사용할 수 있습니다.