해시(Hash)

참고

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
• 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

Lee → 해싱함수 → 5
Kim → 해싱함수 → 3
Park → 해싱함수 → 2
...
Chun → 해싱함수 → 5 // Lee와 해싱값 충돌

• 충돌(collision) 현상
  • 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함
• 해시 테이블을 쓰는 이유
  • 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
  • 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능
• 언제나 동일한 해시값 리턴, index를 알면 빠른 데이터 검색이 가능해짐
• 해시테이블의 시간복잡도
  • O(1) - (이진탐색트리는 O(logN))

충돌 문제 해결

• 체이닝(Chaining) : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)

  

• 오픈 어드레싱(Open Addressing) : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용 (해당 키 값에 저장되어있으면 다음 주소에 저장)

  

  • 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
    • 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.
    • 특징 : Cluster(클러스터) 현상이 매우 잘 발생한다.
  • 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
    • 선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.
    • 특징 : 서로 다른 해시 값을 갖는 데이터에 대해서는 클러스터가 형성 되지 않도록 하는 효과가 어느 정도 있지만, 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 발생

해시 구현

<해시 테이블>

• 해쉬 함수: key % 8
• 해쉬 키 생성: hash(data)

hash_table = [0 for i in range(8)]

def hash_func(data):
    return hash(data) % 8

def set_data(data,value):
    key = hash_func(data)
    hash_table[key] = value

def get_data(data):
    key = hash_func(data)
    return hash_table[key]

<체이닝>

hash_table = [0 for i in range(8)]

def hash_func(key):
    return key % 8

def set_data(data,value):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key] != 0:
        for i in range(len(hash_table[hash_key])):
            if hash_table[hash_key][i][0] == hash_idx:
                hash_table[hash_key][i][1] = value
                return True
        hash_table[hash_key].append([hash_idx,value])
        return True
    else:
        hash_table[hash_key] = [[hash_idx,value]]
        return True

def get_data(data):
    hash_idx = hash(data)
    hash_key = hash_func(hash_idx)
    if hash_table[hash_key]:
        for value in hash_table[hash_key]:
            if value[0] == hash_idx:
                print(value[1])
                return value[1]
        print("None")
        return None
    else:
        print("None")
        return None