자료구조 11. 해싱

코드

• 모든 코드는 깃허브에서 확인하실 수 있습니다.

해싱

• 키(key) 값을 이용해 항목을 저장하고 접근하는 자료구조
• 해시 함수: 키 값을 해시 주소로 변경하는 함수
• 해시 테이블(hash table): 해시 함수의 결과에 의해 접근이 가능한 구조
  • 딕셔너리(dictionary) 또는 맵(map)으로 불리기도 함
  • 슬롯(slot): 값을 저장할 수 있는 공간
  • 버켓(bucket): 각각의 해시 주소에 해당하는 값을 저장할 공간
    • 슬롯의 집합

해싱의 문제점

• 충돌(collision): 서로 다른 키에 대해 같은 해시 주소가 나오는 문제
• 오버플로우(overflow): 충돌이 버켓에 할당된 슬롯의 수보다 많이 발생하는 것
  • 반드시 오버플로우를 해결할 방법이 필요
• 좋은 해시 함수라면 충돌이 적고 해시 주소가 고르게 분포되어야 하며 계산이 빨라야 함

해시 함수

• division method
  • key를 테이블의 크기로 나눈 나머지를 주소로 사용
• 비트추출 함수
  • 키를 이진수로 간주하여 임의의 위이 k개의 비트를 해시 주소로 사용
• 문자열 해시 함수
  • 문자열의 문자를 다 더한 후, 테이블의 크기로 나눈 나머지를 주소로 사용

충돌 해결

• 선형 조사법
  • 해시 함수를 통해 생성된 주소에 이미 값이 있을 경우 다음 주소에 값을 저장하는 방법
• 체이닝
  • 각 버켓에 연결 리스트를 할당하여 값을 저장하는 방법

문자열 해시 함수 + 체이닝 예시

• 해시 함수

  unsigned int HashFunction(const char* key)
  {
      unsigned long int value = 0;
    
      for (int i = 0; i < strlen(key); i++)
      {
          value += key[i];
      }
    
      return value % TABLE_SIZE;
  }
  

• 해시 테이블 구조체

  typedef struct Node
  {
      char* key;
      int value;
      struct Node* next;
  } Node;
    
  typedef struct
  {
      Node** buckets;
  } HashTable;
  

• Init

  HashTable* Init()
  {
      HashTable* table = (HashTable*)malloc(sizeof(HashTable));
      table->buckets = (Node**)malloc(TABLE_SIZE * sizeof(Node*));
      for (int i = 0; i < TABLE_SIZE; i++)
      {
          table->buckets[i] = NULL;
      }
      return table;
  }
  

• Add

  void Add(HashTable* table, const char* key, int value)
  {
      unsigned int bucket = HashFunction(key);
      Node* newNode = (Node*)malloc(sizeof(Node));
      newNode->key = _strdup(key);
      newNode->value = value;
      newNode->next = table->buckets[bucket];
      table->buckets[bucket] = newNode;
  }
  

• Search

  int Search(HashTable* table, const char* key)
  {
      unsigned int bucket = HashFunction(key);
      Node* node = table->buckets[bucket];
      while (node != NULL)
      {
          if (strcmp(node->key, key) == 0)
          {
              return node->value;
          }
          node = node->next;
      }
      return -1;
  }
  

• Delete

  void Delete(HashTable* table, const char* key)
  {
      unsigned int bucket = HashFunction(key);
      Node* node = table->buckets[bucket];
      Node* prev = NULL;
    
      while (node != NULL && strcmp(node->key, key) != 0)
      {
          prev = node;
          node = node->next;
      }
    
      if (node == NULL)
      {
          return;
      }
    
      if (prev == NULL)
      {
          table->buckets[bucket] = node->next;
      }
      else
      {
          prev->next = node->next;
      }
    
      free(node->key);
      free(node);
  }