맵Map과 해시Hash의기본 개념

맵Map

• 해시맵(Hash map) : 해시테이블(Hash table), 딕셔너리(Dictionary)
• 키(key)와 값(value)을 대응시켜 자료를 보관하는 자료 구조(like 사전)
• 정보를 찾는 기준이 되는 키와 그 키에 연결된 값으 대응 관계를 저장
  • 예: 물품 이름(키)와 가격(값) 또는 재고(값)과. 학생 이름(키)와 성적(값)

 

• 키는 중복되지 않음
  • 존재하는 키에 새 값을 넣으면 기존 값은 지워지고 새 값으로 덮어 써짐

 

• 키를 추가적으로 저장하기 때문에 공간 복잡도는 올라가지만, 모든 값을 검색할 필요가 없기 때문에 시간 복잡도, 즉 효율성이 개선됨.

해싱Hashing

• 해시 함수(hash function)
  • 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
  • 이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 함.

 

• 해시 테이블(hash table)
  • 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시 값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료 구조