학습 내용

파이썬 내 hash map 은 체이닝 방식 로드 밸런싱이 좋아야 한다. 속도가 빨라야 한다.

데이터구조

해시테이블

학습자료

[자료구조 알고리즘] 해쉬테이블(Hash Table)에 대해 알아보고 구현하기
[자료구조] Hash Table (해시 테이블) 이란?
[자료구조] Java 해쉬(Hash) 기본 개념과 구조 (분리연결법)
Java HashMap은 어떻게 동작하는가?
해쉬 테이블의 이해와 구현 (Hashtable)
[알고리즘] Hash table

구현 예제

https://github.com/huhuta/dudaji/blob/develop/data-structure/hash-table/hashtablepractice.py
https://github.com/keon/algorithms/blob/master/algorithms/map/hashtable.py
https://github.com/keon/algorithms/blob/master/algorithms/map/separatechaininghashtable.py

python 내장 해시테이블 dictionary

[점프투파이썬] 딕셔너리 자료형

추가자료

아스키코드

연습

해시테이블

체이닝 방식으로 구현하기
오픈어드레싱 방식으로 구현하기 (선택)
unittest를 통해 구현체에 대한 검증 (push, pop, peek, (array 기반인 경우) expand, 저장되지 않은 값의 참조 등)

코딩

chaining

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


class HashTable():

  def __init__(self, size=7):
    self._table = [[] for _ in range(size)]
    self.size = size

  def set(self, key, value):
    
    new_node = Node(key, value)

    box, item, in_index = self.find(key)
    
    if item == None:
      box.append(new_node)
    else:
      item = new_node
    


  def get(self, key):

    _, item, in_index = self.find(key)
    if item == None:
      return None

    return item.value


  def delete(self, key):

    box, item, in_index = self.find(key)
    if item is None:
      return False
    
    del_item = box.pop(in_index)
    return del_item.value


  def find(self, key):
    
    hash_key = hash(key)
    index = hash_key % self.size

    box = self._table[index]
    
    cnt = len(box)
    for in_index in range(0, cnt):
      item = box[in_index]
      if item.key == key:
        return box, item, in_index 

    return box, None, -1


hash_table = HashTable()

def hash_set(key, value):
  return hash_table.set(key, value)
    

def hash_get(key):
  return hash_table.get(key)


def hash_delete(key):
  return hash_table.delete(key)