Hello Coding 그림으로 개념을 이해하는 알고리즘 Study Note 05

Chapter 5 해시 테이블 (Hash table)

해시 함수

- 자료구조 해시 테이블을 구현하기 위한 함수

- 문자열(string)을 받으서 숫자를 반환하는 함수

- 문자열에 대해 숫자를 할당(mapping)

해시 테이블

- 해시 함수 + 배열을 결합하여 만듬

- 충돌을 줄이는 해시 함수가있어야한다

- 해시 테이블은 키(key)와 값(value)를 가진다

- 해시 맵(hash maps), 맵(maps), 딕셔너리(dictionaries), 연관 배열(associative arrays) 라는 이름으로도 알려져 있음

- 속도가 빠르다, 평균적인 해시 테이블의 성능은 O(1) 상수시간이다

- 주요 프로그래밍 언어에서 구현되어 있음, 파이썬에는 딕셔너리라고 불리는 해시 테이블이 있다

- 사용률이 0.7보다 커지면 해시 테이블을 리사이징 하는 편

해시 테이블 사용 예

- 데이터 저장과 조회 ex) 전화번호부, 인터넷 주소와 ip주소

- 중복항목 방지

- 데이터 캐시로 사용 (자주 사용되는 정보를 다시 계산하지 않고 저장했다가 사용)

Chapter 5 정리

해시 테이블은 빠르고 여러가지로 모형화 할 수 있기 때문에 아주 강력한 자료 구조 이다

해시 테이블의 평균적인 성능은 상수 시간이다 (정말 빠르다)

해시 테이블을 위해서는 잘 짜여진 해시 함수(좋은 분포를 가진)와 사용율에 따른 리사이징이 필요하다

다양한 프로그래밍 언어에서 구현되어 지원한다

다양한 용도로 사용되고 있다

SHA 라는 해시 함수를 공부 해보면 좋다