나만의 고유한 컨텐츠를 누군가가 그대로 퍼가서 자기 채널에 올렸을 때, 나는 그 즉시 그 사실을 알아야 하지 않을까? 이런 고민은 우리가 알고 있는 큰 플랫폼들이 당연히 했을 고민일 것이고 그럼 그걸 프로그래밍으로 어떻게 처리했을까. 이럴 때 바로 해시 테이블(Hash Table)을 사용한다고 한다. 그전에 해시(Hash)의 의미부터 가볍게 풀어보면,
hash, hashcode를 얼핏 얼핏 들어보셨을 것 같다.(equal과 같이 쓸 때)
hash function(간단하게 hash)는 임의의 길이의 데이터를 딱 고정된 길이의 데이터로 바꿔주는 것이라고 설명하겠다. 이 hash 함수를 돌려서 return 받은 게 바로 해시값, 다른 말로는 해시 코드, 해시섬 등등이라고 한다. 블록체인도 이 hash 로직을 이용하는 것이다.
그럼 해시테이블(Hash Table)이란?
검색하고자 하는 key 값을 입력받아 hash 함수를 돌려 return 받은 hashcode를
배열의 Index로 환산해서 데이터에 접근하는 방식의 자료구조
- Hash Table의 필수조건은 고정된 크기의 배열을 우선 선언하는 것이다.
- 여기서 key 값은 문자열이나 숫자, 혹은 파일 데이터도 될 수가 있다.
- 배열의 Index로 환산? 이라고 하면 뭔가 말이 어려워 보이는데 그냥 hashcode를 배열의 size로 나눈 나머지다. (그런데 이건 확실하지 않지만 왜인지 로직이나 상황에 따라서 다르게 환산할 수도 있을 것 같다.)
해시코드 % 배열 Size
해시테이블(Hash Table)의 장점
검색 속도가 무지 빠르다.
hash 함수를 통해서 return 받은 hashcode는 정수(int)로 구성되는데, 이 hashcode는 환산 후 배열의 Index로 그대로 사용되기 때문에 검색 자체를 어떻게 보면 할 필요가 없다. 데이터의 위치에 다이렉트로 접근할 수 있기 때문이다.
해시테이블(Hash Table)의 고민
- 그럼 이 배열에 데이터들을 적재한다고 하면 어떤 데이터는 1번 방, 어떤 건 2번 방, 이런 식으로 규칙을 정해야 할 텐데 한 방에 너무 많은 데이터가 들어가게 되면 Collision(충돌)이 많이 일어나게 될 것이다.
- Collision이란 따라서 하나의 배열방에 겹쳐서 저장되는 것을 말한다.
- Hash Table의 장점은 검색시간(시간복잡도)가 O(1)이라는 점인데 Collision이 많이 발생하게 되면
최악의 경우 O(n)까지 늘어나게 된다.
따라서 좋은 Hash Algorithm은
입력받은 key를 가지고 얼마나 잘 분배하는지로 결정된다.
이 말인 즉, Collision을 최소화 하는 알고리즘이라는 것과 같은 말이겠다.