[Coding Interview University] 해시테이블 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 해시테이블 (hash table)

: 효율적인 탐색을 위한 자료구조로서, key를 value 에 대응시킴

: 최악의 경우 O(n) // n은 키의 개수

: 최선의 경우 O(1)

 

🫧 연결리스트와 해시 코드 함수로 구현

1) 키의 해시 코드 계산

• 키의 자료형은 보통 int or long
• 키의 개수 무한 (int 는 유한)

2) hash(key) % array_length 방식으로 해시 코드 이용해 배열의 인덱스 구함

• 서로 다른 두 개의 해시 코드가 같은 인덱스 가리킬 수 있음

3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트 존재

• 키와 값을 해당 인덱스에 저장 (반드시 연결리스트 이용!)
• 💥 충돌 : 서로 다른 두 개의 키가 같은 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

⇒ 키에 상응하기 위해서 위를 반복!

⇒ 주어진 키로부터 해시 코드를 계산, 해시 코드를 이용해 인덱스 계산, 해당 키에 상응하는 값을 연결 리스트에서 탐색

균형 이진 탐색 트리 (balanced binary search tree)
: 탐색 시간은 O(logN)
: 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 적은 공간 사용 가능
: 키의 집합을 특정 순서대로 접근 가능

 

🫧 해시테이블 구현하기

Linear probing을 사용하여 배열로 구현해보기

class Node:
    def __init__(self, key, value, next):
        self.key = key
        self.value = value
        self.next = next

➡️ hash(k, m) - m은 해시 테이블의 크기

// map의 크기: map.size()
map.size // 4
map.length // undefined

➡️ add(key, value) - 키가 이미 존재한다면, 값을 갱신한다.

Hashtable ht = new Hashtable();
ht.Add("irina", "Irina SP");
ht.Add("tom", "Tom Cr");

if (ht.Contains("tom"))
{
    Console.WriteLine(ht["tom"]);
}

➡️ exists(key)

map에 해당 key의 value 존재 여부: has(key)
map.has(str); // true
map.has(obj); // true
map.has('none'); // falsemap의 크기: map.size()
map.size // 4
map.length // undefinedmap의 크기: map.size()
map.size // 4
map.length // undefined

➡️ get(key)

• Map 객체는 key-value로 이루어진 해시테이블
  • set(): key-value pair를 map에 삽입
  • get(): key값으로 value를 찾아 리턴
  • key에 들어갈 수 있는 자료형은 number, string, function, object, NaN 등이 가능

  let number = 0;
  let str = 'string';
  let obj = { a: 1 };
  let func = () => {
      console.log('func');
  };
  
  map.set(number, 4); //key에 number 가능
  map.set(str, 1); // key에 string 가능
  map.set(obj, 2); //key에 object 가능
  map.set(func, 3); // key에 함수 가능
  map.set(number, 0); // 덮어쓰기 가능
  
  console.log(map); // Map(4) {0 => 0, "string" => 1, {…} => 2, ƒunc => 3}
  
  map.get(str); // 1
  map.get(obj); // 2
  map.get('none'); // undefined  
  map.get({ a: 1 }); // undefined, obj !== { a: 1 }
  

➡️ remove(key)

using System;
using System.Collections;
public class SamplesHashtable
{

   public static void Main()
   {
      // Creates and initializes a new Hashtable.
      var myHT = new Hashtable();
      myHT.Add("1a", "The");
      myHT.Add("1b", "quick");

      // Removes the element with the key "3b".
      myHT.Remove("3b");

   }
}