[자료구조] 해시(Hash)란 무엇인가

https://s1m0hya.tistory.com/27

오늘은 보안에서 가장 자주 사용되는 해시함수의 근본인 자료구조 해시를 배워보겠다

 

📚 해시 테이블이란

컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

 

 

 

💡 해시 테이블의 원리

 

해시 테이블은 파이썬의 딕셔너리(dictionary)와 같다

 

menu = {"apple": 1000, "potato": 500, "melon": 9000, "iceCream": 1500}

 

 해시 테이블은 자료의 접근이 O(1)이다

menu에서 melon의 가격을 찾고 싶다면 menu의 인덱스를 모두 찾지 말고 key값이 melon인 것에 접근하면 되기 때문이다.

 

이런 해시 테이블의 원리는 hash 함수에 있다.

파이썬 콘솔에서 hash() 함수에 "melon"인자를 넣어보자

 

 

 

그럼 무작위의 긴 숫자가 나올 것이다.

저 숫자는 PC마다 다르게 나올 테니 사람마다 다르게 나올 것이다.

이제 저 무작위의 숫자가 배열의 인덱스를 정하게 되는 것이다.

 

즉 해시테이블(딕셔너리)에 요소를 추가하면 그 요소의 키값을 hash()에 넣어

나온 숫자 값이 딕셔너리의 인덱스를 정해서 그 인덱스에 key와 value를 저장하는 것이다.

이제 저 키 값을 크기가 4인 배열에 넣어주려면 이렇게 계산하면 된다. 

 

 

 

 

 이러면 크기가 4인 배열에 인덱스 1에 melon과 그 value가 저장되는 것이다.

 

❓ 엥 앞에 코드 보시면 인덱스 2번째에 저장했는데요??

 

논리적으로 그렇겠지만 물리적, 내부적으로는 컴퓨터는 hash() 함수가 반환된 값으로

키의 인덱스를 저장하고 그 값을 찾을 때도 반환된 값으로 찾게 되는 것이다.

그래서 내부적으로는 배열 탐색과 같다.

 

그러면 여기서 또 의문점이 하나 들 것이다.

 

 

 

 

❓ hash() 함수로도 똑같은 인덱스가 나오면요?? 그럼 덮어씌워지지 않나요?

 

 그렇다. 이런 원리면은 같은 인덱스끼리는 덮어씌워지어 먼저 저장된 데이터는 지워진다.

이것을 우리는 충돌이라고 부른다.

 

그래서 인덱스끼리는 배열로 저장하고 같은 인덱스끼리는 LinkedList로 되어있다.

같은 인덱스가 생길 때마다 노드로 추가하는 것이다.

 

 

 

 

Θ Ω 해시 테이블의 시간복잡도

 

https://mingcoder.me/2018/04/29/Programming/Algorithm/hashtable/

 

😀 충돌이 일어나지 않았으면(평균적인 경우) 

 

탐색) 인덱스로 값을 탐색하니 O(1)

삽입) 해시 함수를 통해 인덱스가 정해지니 O(1)

삭제) 인덱스와 인덱스 안에 값만 지워주면 되니 O(1) (배열처럼 지워졌다고 순서를 다시 정리할 필요가 없다)

 

😡 충돌이 일어날 경우(최악의 경우)

 

탐색) 인덱스로 값을 탐색한 후 링크드리스트를 순차탐색해야한다. 결국 링크드리스트의 길이 n만큼 시간이 소요된다. O(N)

삽입) 링크드리스트의 탐색을 거치게 되니 링크드리스트 탐색 시간복잡도와 같다. O(N)

삭제) 링크드리스트의 탐색을 거치게 되니 링크드리스트 탐색 시간복잡도와 같다. O(N)

 

 

👍 해시 테이블의 장점

• 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다.
• 중복을 막을 수 있다.(충돌을 피하는 설계를 하게 되니 가장 이상적이다)
• 서버에 작업을 시키지 않고 자료를 캐싱할 수 있다.

 

👀 해시 테이블의 사용 예시

☝ 해시 테이블로 조회하기

 

휴대폰의 전화번호부를 생각해보면,
사람의 이름과 그 사람에 관련된 전화번호를 추가한다.
사람 이름을 입력하면 그 이름과 관련된 전화번호를 알려준다.

 

또는

 

메뉴판의 메뉴를 생각해보면

메뉴 이름과 메뉴 가격을 추가한다.

메뉴 이름을 입력하면 그 메뉴의 가격이 알려주는 메뉴판 역할을 해줄 수 있다.

 

☝  중복된 항목을 방지하기

 

투표소에서 어떤 사람이 투표를 했는가 안 했는가를 판단하기 위해서 배열이나 리스트를 사용하면 긴 목록을 뒤져봐야 하지만, 이름을 해시 테이블에 저장하면 해시 테이블에 이름이 있는지, 없는지 즉시 알려준다.

 

☝   해시 테이블을 캐시로 사용하기

캐싱은 작업 속도를 올리는 일반적인 방법이다. 모든 대형 웹사이트는 캐싱을 사용한다.
그리고 그 자료는 바로 해시 테이블에 저장된다.
캐싱된 자료가 있으면 그 자료를 전송하고 없으면 서버에 요청하는 식으로 사용한다.

 

🔗 참조 : 해시 테이블(hash table)[클릭]

  

 

 

📑 해시 테이블의 구현 코드(feat : 파이썬)

 

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if key == k:
                return v

class LinkedDict:
    def __init__(self, length):
        self.items = []
        for i in range(length):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)


    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

menu = LinkedDict(4)
menu.put("apple", 1000)
menu.put("potato", 500)
menu.put("melon", 9000)
menu.put("iceCream", 1500)
print(menu.get("apple"))	# 1000
print(menu.get("potato"))	# 500