제1 1 장 산 목록 (2) 산 목록

해시 표 로 직접 주소 지정 표 의 두 문 제 를 해결 하 다.그러나 이 로 인 한 산열 값 의 충돌 문제.
가장 간단 한 해결 방법 은 링크 법 과 다음 절 에 소개 되 는 개방 주소 법 이다.
링크 법, 즉 같은 슬롯 에 흩 어 져 있 는 모든 요 소 를 하나의 링크 에 넣 는 것 이다.
링크 는 무질서 합 니 다. 원 소 를 찾 을 때 링크 를 옮 겨 다 녀 야 합 니 다.
삭제 함수 에 대해 서 는 인자 가 삭제 할 노드 라면 링크 가 양 방향 이면 삭제 작업 은 O (1) 내 에 완 료 될 수 있 습 니 다.
아래 삭제 함수 에서 매개 변 수 는 키워드 로 더욱 편리 합 니 다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 20

//        
typedef struct _ListNode {     
     struct _ListNode *prev, *next;
     char *key;
     char *val;
} ListNode;

//                
ListNode *hashmap[SIZE];

//         Java String HashMap      
//             ( 0         )
//   h       
unsigned hashcode(char *key)
{
     // Ensure >> is logical shift
     unsigned h = 0;

     // String.hashcode()
     do h = 31 * h + *key++;
     while (*key != '\0');     

     // HashMap.hash()
     h ^= (h >> 20) ^ (h >> 12);
     return h ^ (h >> 7) ^ (h >> 4);
}

ListNode * hashmap_search(char *key)
{
     unsigned h = hashcode(key) % SIZE;
     ListNode *node = hashmap[h];
     while (node != NULL) {
          //     ,strcmp  0
          if (strcmp(node->key, key) == 0) {
               return node;
          }
          node = node->next;
     }
     return NULL;
}

char * hashmap_insert(char *key, char *val)
{
     unsigned h = hashcode(key) % SIZE;
     printf("Insert %s - %s to bucket %d
", key, val, h); // Find duplicate key, replace it then return old value ListNode *node = hashmap_search(key); if (node != NULL) { char *oldVal = node->val; node->val = val; return oldVal; } // Not found, create new node to save key&val pair ListNode *newNode = malloc(sizeof(ListNode)); newNode->prev = NULL; newNode->key = key; newNode->val = val; if (hashmap[h] == NULL) { hashmap[h] = newNode; } else { hashmap[h]->prev = newNode; newNode->next = hashmap[h]; hashmap[h] = newNode; } return val; } char * hashmap_delete(char *key) { ListNode *node = hashmap_search(key); if (node != NULL) { // Set prev node's next to node's next if (node->prev == NULL) { unsigned h = hashcode(key) % SIZE; hashmap[h] = node->next; } else { node->prev->next = node->next; } // Set next node's prev to node's prev if (node->next != NULL) node->next->prev = node->prev; return node->val; } return NULL; } void hashmap_print() { int i; for (i = 0; i < SIZE; i++) { ListNode *node = hashmap[i]; while (node != NULL) { printf("%s - %s, ", node->key, node->val); node = node->next; } if (hashmap[i] != NULL) printf("%d bucket
", i); } printf("
"); } int main(void) { // Compare to String.hashcode() in JDK printf("%d
", hashcode("helloworld")); hashmap_insert("aabb", "value1"); hashmap_insert("ccdd", "value2"); hashmap_insert("i'mcdai", "value3"); int i; for (i = 0; i < 2 * SIZE + 5; i++) { char *key = calloc(sizeof(char), 10); char *val = calloc(sizeof(char), 10); sprintf(key, "%s%d", "aabbcc", i); sprintf(val, "%s%d", "val ", i); hashmap_insert(key, val); } // Insert duplicate key printf("%s
", hashmap_insert("i'mcdai", "dupdup")); hashmap_print(); printf("%s
", hashmap_search("i'mcdai")->val); printf("%s
", hashmap_search("aabbcc18")->val); //printf("%s
", hashmap_search("NOTFOUND")->val); // All in bucket 18: aabbcc10 => aabbcc0 => i'mcdai printf("%s
", hashmap_delete("aabbcc10")); printf("%s
", hashmap_delete("i'mcdai")); hashmap_print(); return 1; }

좋은 웹페이지 즐겨찾기