해시(Hash)

1. 해시란?

데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것

Lee → 해싱함수 → 5
Kim → 해싱함수 → 3
Park → 해싱함수 → 2
...
Chun → 해싱함수 → 5 // Lee와 해싱값 충돌

① 해당 데이터의 해시값을 해시 함수를 이용하여 계산한다.

② 이 해시값을 주소로 하는 위치에 데이터를 저장한다.

③ 저장 후에 검색할 때 데이터의 해시값을 계산해서 바로 해당 위치로 이동할 수 있다. O(1)

 

하지만 데이터가 많아지면 다른 데이터임에도 같은 해시값이 나오는 충돌이 발생한다.

그래도 해시 테이블을 쓰는 이유는?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위해

하드디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.

2. 충돌 문제 해결 방법

① Chaining: 연결리스트로 노드를 계속 추가. 메모리 문제 발생

② Open Addressing: 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용

• 선형 조사

  

• 이차원 조사

  

• 더블 해싱

  

해시는 무결성 검사, 클라우드 스토리지에서 동일한 파일 식별 및 수정된 파일 검출,

db 비밀번호 저장, 블록체인, git 등에서 사용된다.