해시(Hash)

해시란?

해시 함수에 의해 얻어지는 값

해시 함수란?

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터(해시 값)로 매핑하는 함수

• 같은 입력값에 대해서 같은 출력값을 보장한다

해시 충돌(Collision)

서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황

데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함

해시 테이블 사용 이유

• 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있다.
  ex) HDD, Cloud에 존재하는 많은 데이터들을 유한한 개의 해시값으로 매핑하여 작은 크기의 캐쉬 메모리로 프로세스 관리 가능
• 검색, 삽입, 삭제가 빠르다.
  평균 시간복잡도 : O(1)
• 키와 해시값이 연관성이 없어 보안에도 사용할 수 있다.

충돌 문제 해결

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

• Open Addressing : 추가적인 공간을 만들지 않고 기존에 해시 테이블 공간만으로 충돌을 해결하는 것

  • 선형 조사 : 충돌이 일어난 바로 뒷자리를 보는 것
    h(x) = ( h(x) + i ) mod m

  • 이차원 조사 : 보폭을 이차함수에 의해 넓혀가면서 본다
    h(x) = ( h(x) + i² ) mod m

참고 링크

https://hee96-story.tistory.com/48