해시 테이블

Hash Table

자료 구조 해시 테이블이란 무엇인가? 알아보자

Hash

먼저, 해시(Hash) 다.
해시(해시 함수)는 임이의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 의미한다. 아무리 큰 숫자, 작은 숫자를 넣더라도 정해진 크기의 숫자가 나온다.

이러한 해시 함수를 적용해 나온 고정 길이의 값을 해시값, 해시 코드, 해시섬 등으로 부른다.

해시 함수는 입력값의 범위가 출력값의 범위보다 넓기에 서로 다른 입력값에도 동일한 값이 출력되는 경우가 존재한다. 이러한 경우 충돌되었다고 하며 연결 리스트로 연결하는 방식으로 해결한다.

Hash Table

해시 테이블이란 해시 함수의 특징을 이용해 변환값을 색인으로 삼아 KEY-VALUE를 저장하는 자료구조를 의미한다. KEY를 알고 있다면 빠르게 VALUE를 저장/삭제/조회할 수 있다. 하지만 KEY는 순서가 없다.

매우 빠른 속도를 자랑하기에 대부분의 프로그래밍 언어에서는 해시 자료 구조를 갖고 있다.

• Python - Dictionary
• JavaScript - Map, Object (KEY에 문자열만 가능)
• Java, Go, Scala - Map
• Ruby - Hash

충돌

이러한 해시 테이블의 문제는 입력 데이터에 비해 해시 테이블이 작은 경우에 발생하는, 충돌이다.

위의 예시에서 입력 데이터가 10에서 19까지가 아닌 10에서 99까지라면 해시 테이블[1]에는 11, 21, 31, 41, 51, … 91 이 저장된다. 이 경우 KEY 값이 있다고 해도 원하는 VALUE인지 확인하는 과정을 한번 더 거쳐야 된다. 추가된 과정만큼 시간과 메모리도 추가될 것이다.

그래서 해시 테이블을 사용할 때는 충돌을 방지해야 한다. 해시를 바꾸거나, 해시 테이블을 바꾸거나

1. Hash 바꾸기

(땜빵 느낌’s) 해시 함수를 바꿔 중첩된 KEY 값이 발생하지 않도록 한다.
=> 입력되는 데이터가 많아지면 다시 발생할 수 있음

2. Hash Table 바꾸기

• 1. KEY-VALUE 중첩 허용

  배열 || 연결 리스트 활용

• 1. KEY-VALUE 중첩 불허

  Hash Table의 크기를 낭낭하게 준비해두기 !
  미리 빈 공간을 마련해둔다.

  • 1. 일정한 폭만큼 차례대로 이동해 빈 공간 만들기
  • 2. 해시의 저장 폭을 제곱으로 바꿔 빈 공간 만들기
  • 3. 해시를 해시해 새로운 주소를 할당하기

Hash in JS

Javascript에서는 Object 와 Map 을 활용해 해시를 구현한다. 하지만 해시가 필요하면 대부분 객체 Object {} 를 활용해 해결했다. KEY-VALUE가 직관적이고 성능도 좋아서 대부분의 문제 해결이 가능했다. 그러다보니, Map을 사용할 필요성을 못느꼈다.

하지만 알고리즘 문제를 풀면서 메모리에 신경쓰게 되니 점점 Map에 눈길이 가고 있다. 객체를 사용하면 키값을 문자열로 변경해야하는데 Map에서는 그럴 필요가 없고 그대로 사용하면 된다는 점이 큰 장점으로 느껴지기 시작했다. (성장해버린 나…?)

아직 Map이 익숙하진 않지만 점점 사용 빈도를 늘려갈 생각이다. 간바레 !