이 크기 조정 기능은 어떻게 수정합니까?

Question

데이터 구조를 배우고 있습니다. 해시 테이블 (chaining/buckets)에 대한 크기 조정 함수를 만들어야합니다. 내 코드는 컴파일되지만 테이블 크기는 변경되지 않습니다. 누군가가 모양을 가지고 내가 크기 조정 기능에서 누락 된 것에 대한 팁을 줄 수 있습니까? 고맙습니다!

struct hlink { 
    TYPE value; 
    struct hlink *next; 
}; 

struct hashTable { 
    struct hlink **table; 
    int tableSize; 
    int count; 
}; 


void initHashTable (struct hashTable *ht, int size) { 
    assert (size > 0); 

    //allocate memory for table 
    ht->table = (struct hlink **) malloc(size * sizeof(struct hlink *)); 
    assert(ht->table != 0); 

    //initialize empty link list 
    int i; 
    for (i = 0; i < size; i++) 
    { 
     ht->table[i] = 0; 
    } 

    //set tableSize to be size 
    ht->tableSize = size; 
    ht->count = 0; 
} 


    void _resizeHashTable(struct hashTable *ht) 
{ 
    //create and initialize new tablesize 
    int new_tblSize = 2 * ht->tableSize; 

    //old list 
    struct hlink **oldList = ht->table; 

    //new list 
    struct hlink **newList = (struct hlink **) malloc(new_tblSize * sizeof(struct hlink*)); 

    //Copy old values to new table 
    for (int i=0; i < new_tblSize; i++) 
    { 
     //compute hash value to find the new bucket 
     int hashIndex = HASH(oldList[i]->value) % new_tblSize; 
     if (hashIndex < 0) 
      hashIndex += new_tblSize; 

     newList[i]->value = oldList[i]->value; 
     newList[i]->next = newList[hashIndex]; 
    } 

    //Assign table and tablesize back to the old table 
    free(ht->table); 
    ht->table = newList; 
    ht->tableSize = new_tblSize; 

} 


void hashTableAdd (struct hashTable *ht, TYPE newValue) 
{ 
    // compute hash value to find the correct bucket 
    int hashIndex = HASH(newValue) % ht->tableSize; 
    if (hashIndex < 0) 
     hashIndex += ht->tableSize; 

    struct hlink * newLink = (struct hlink *) malloc(sizeof(struct hlink)); 
    assert(newLink != 0); 

    newLink->value = newValue; 
    newLink->next = ht->table[hashIndex]; 

    ht->table[hashIndex] = newLink;  //add to bucket 
    ht->count++; 


    if ((ht->count/(double) ht->tableSize) > 8.0) 
     _resizeHashTable(ht); 
} 

Answer 1

이전 테이블을 비우지 않았습니다. 방금 할당 한 방을 비우고 있습니다.

ht->table = new_tbl; 
... 
free(new_tbl); 

당신은

free(ht->table); 
ht->table = new_tbl; 

당신은 또한 당신의

//Copy old values to new table 
for (int i=0; i < ht->tableSize; i++) 
{ 
    new_tbl[i] = ht->table[i]; 
} 

에 문제가 있어야하는 대신이 테이블 버킷 위와 같이 엔트리 복사하는 것만으로는 충분하지 않습니다,하지만 각 항목 버킷 링크 목록은 새 테이블 크기와 잠재적 인 새로운 해시 인덱스가 있으므로 다시 해시해야합니다.

int hashIndex = HASH(newValue) % ht->tableSize; 

나는 크기 조정 때 일시적으로, 각 오래된 양동이와 각 링크 목록 항목하지만 가서 새 테이블로 이동하는 것이 좋습니다. 각 항목에 대해 이전 테이블의 버킷 인덱스는 "% ht-> tableSize"가 다르기 때문에 새 테이블의 버킷 항목과 다를 수 있습니다.

resize()를 실행하는 동안 이전 테이블의 링크 목록 할당을 관리해야합니다. 새 테이블에서 다시 사용할 수 있지만 여기서 적절한 코딩은 어려울 수 있습니다. 다음은

는

P. S.는 또한 또한 테이블의 크기를 두 배로 그러나 그것을 4 배하지 않는 것이 좋습니다

if (ht->count > (ht->tableSize * 8)) 

대신

if ((ht->count/(double) ht->tableSize) > 8.0) 

P. S.의 추천 ... 그냥 몇 가지 개선 아이디어입니다. 또한 테이블 크기를 소수로 사용하는 것이 좋습니다. "% ht-> tableSize"를 소수로 사용하면 약한 해시 함수의 분산을 향상시킬 수 있습니다.

Quadrupling에는 hashTableDelete()를 추가 할 때 좋은 반응이 있습니다. delete 함수를 사용하면 resize 함수를 다시 호출 할 수 있지만 이번에는 테이블이 축소됩니다. 성장 임계 값 (예 : 테이블 크기 * 8)과 수축 임계 값이 다른 것이 중요합니다. 만약 테이블 크기가 동일하다면, 테이블이 그 중요한 크기 일 때 추가하고 삭제해야 할 때 "해시의 스레 싱"을 얻을 수 있습니다. 나는 3, 11, 61, 251, ... (4 ** N 이하의 소수), 1, 7, 31, 119, ... (2 이하 소수)와 같은 수준에서 성장 한계점을 갖고 싶습니다. 4 ** N), 따라서 테이블이 커지고 축소 될 때 최소 해싱을 유지합니다.