[Algorithm] Hash?

Hash

hash란 단방향 암호화 기법으로 hash 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꾸는 것으로 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있어 빠른 속도로 문제를 처리할 수 있습니다.

 

예를 들어 어떤 한 가게에서 손님이 물건을 사러 왔을 때 물건의 가격이 적혀져있는 장부를 찾아서 가격을 봐야한다고 가정할 때, 만약 장부가 정렬되어 있지 않다면 O(n)만큼의 시간, 정렬되어 있다면 O(log(n))만큼의 시간이 소요될 것 입니다. 이때 필요한 것은 가격을 외우고 있는 사람이 옆에 있는 것인데 hash 함수가 이 역할을 합니다.

hash함수(hash 알고리즘)

정의

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 입력으로 key를 받아 0부터 배열의 크기-1 사이의 값을 출력하는데 이 값을 배열의 크기만큼 변환시킨 것.
• 이때, k값이 h(k)로 hash 되었다고 하고 h(k)는 k의 hash값이라고함.
• 즉, 매핑 전 원래 데이터의 값을 key, 매핑 후 데이터 값을 hash 값, 매핑하는 과정을 hashing이라 함. 

 

특성

• 종류가 다양하고 알고리즘마다 hash 길이가 다름.
•  특정 입력에 대해 항상 같은 해시 값을 리턴함.
• 값들을 골고루 분산시키는 함수일수록 좋음.
• 값들이 뭉쳐져 있을 경우 충돌이 일어날 확률이 높음.

Hash table

• key 1개와 value 1개가 1:1로 연관되어 있는 연관배열 구조를 이용하여 key, value를 저장하는 자료구조
• hash table은 위 그림처럼 key, hash function, hash, value, bucket(slot)으로 구성.
  • key
    • 고유한 값으로  hash function의 input
    • 다양한 길이의 값을 가질 수 있음.
  • hash function
    • key를 hash로 바꿔주는 역할
    • 다양한 길이를 갖고 있는 key를 일정한 길이를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 함.
    • 위 그림에서 John Smith가 전화번호를 찾는 과정을 가정할 때 hash 함수 입력값은 "John Smith", 출력값은 "01", buckets에서 "01"에 해당하는 "521-8976"을 찾아내는 과정을 구현하는 함수 
  • hash
    • bucket(slot)에서 value와 매칭되어 저장됨.
  • value
    • bucket(slot)에 최종적으로 저장되는 값으로 key와 매칭되어 저장, 삭제, 검색, 접근이 가능해야함. 

• key값을 table에 저장할 때 key값을 hash함수에 대입하여 계산한 후 그 결과값을 배열의 인덱스로 사용하여 저장

• h(k)만큼의 공간에 저장되기 때문에 공간 낭비가 매우 적음.
• 평균적으로 O(1)의 시간복잡도를 가지고 있어서 효율성 측면에서 우수함.

 

 

충돌(Hash Collision)

정의

• 다른 k값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 문제점으로 오버플로가 발생했다라고도 함. 
• 예를 들어 k1, k2를 hash하였더니 h(k1)=h(k2) 와 같이 hash table은 key값이 달라도 hash 결과가 같을 수 있는데 특정 key의 bucket에 데이터가 집중되면 hash table의 성능을 떨어뜨림. 

최소화 방법

• Chaing
  • bucket 내에 연결리스트를 할당하여 bucket에 데이터를 삽입하다가 충돌이 발생하면 연결시트로 데이터들을 연결하는 방식.
  • 위 그림에서 Sandra Dee라는 사람의 연락처를 삽입할 때, 충돌이 일어나서 bucket내에서 연결리스트로 데이터를 연결하는 것을 참고
  • bucket이 꽉 차더라도 연결리스트로 계속 연결되기 때문에 데이터의 주소값은 바뀌지 않음. 
  • 상대적으로 적은 메모리를 사용한다는 장점이 있지만 외부 저장 공간 작업을 추가로 해야한다는 단점이 존재.
• 개방 주소법
  • 충돌이 일어날 때 다른 bucket에 데이터를 삽입하는 방식으로 저장할 데이터가 적을 때 유용한 방법.
    • 선형탐색: 충돌이 발생하면 다음 bucket 혹은 몇 개를 건너뛰 후 데이터 삽입.
    • 제곱탐색: 충돌이 발생하면 해시의 제곱만큼 건너뛴 bucket에 데이터를 삽입.
    • 이중해시: 충돌이 발생하면 다른 해시함수를 한 번 더 적용한 결과를 삽입.
  • hash 함수는 또 다른 저장 공간에서의 추가적인 작업이 없다는 장점이 존재하지만 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야하는 단점이 존재. 

 

Hash 알고리즘을 이용하여 푸는 프로그래머스 문제 

참고자료

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

해시 함수