해시 테이블, 해시 맵에 대하여 (Hash table, Hash map)

# 오늘의 개념 : 

Hash table / Hash map

 

 

우선, 해시(hash)가 뭘까 ? 많이 들어보긴 했지만, 정확한 개념을 아직 모르겠다. 뭐든지 왜 이 이름이 붙여졌는지를 파악하면 이해가 쉽다.

 

해시(Hash)

• 어떤 문자열을 더 짧은 길이의 값이나 키로 변환하는 것. (문자열이 같으면 해시값도 동일.)
• 데이터 검색에 있어 매우 효율적
  • 데이터를 key-value 로 저장 , 이때 key값이 배열의 인덱스로 변환되기 때문에 평균 시간복잡도가 O(1).

 

해시 함수 (Hash function)

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.
• 입력값이 조금이라도 변경 시 다른 해시값을 출력.
• 출력된 결과값을 토대로 입력값 유추 불가.
• 해쉬 충돌의 이슈가 있음.
  • Seperate Chaining / Open Addressing 등 (이부분은 다음기회에)

 

해시 테이블

• Key - value 로 저장되는 데이터 구조

• key에 대한 데이타를 찾을때, 해시 함수를 한번만 수행하면 index 위치를 찾아낼 수 있기 때문에, 데이타의 저장과 삭제가 빠름.

출처 : 직접 그렸어요 .. by 나야누리

 

 

해시 맵(Hash map)

• 해시테이블과의 차이점 
  • 동기화 보장 X (비동기)
  • 스레드에 안전하지 않음