자료구조(2)_Hash Table
해시 테이블 ?
- 해시 함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다.
- 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.
- Java의 Map이 해시 테이블의 대표적인 예다.
해시 테이블 특징
- 해시 테이블은 순서없이 Key 와 Value로만 값을 저장하기 때문에 순서가 필요한 데이터에는 적합하지 않다.
- 해시 테이블은 다른 자료구조에 비해 빠른 속도로 삽입, 삭제, 조회가 가능하다.
해시 테이블의 구성
Hash
- Hash란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행된다.
- 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 한 쌍으로 존재하고, Key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1) 이다.
- Key를 Hash function의 input으로 실행 했을 때 나오는 output.
Hash Funtion
- 해시 함수는 키에 대한 해시값을 만드는 함수로 , 키에 대한 해시값을 구하는 과정을 Hashing이라고 한다. 이때 사용하는 함수를 해시함수라고 한다. 즉, 해시함수는 해시를 만드는 함수이다.
- 나눗셈법(Division Method)과 곱셈법(Multiplication Method)이 대표적이다. (충돌해결 방법)
- 입력값 상관없이 고정된 길이의 해시값을 출력한다.
- 복호화가 불가능하다 (단방향 암호화 기법의 특징 )
- 입력값이 일부만 변경되어도 전혀 다른 값을 출력한다. 이 말은 즉, 메시지의 오류나 변조를 탐지할 수 있는 무결성이다.
대표적인 예로는 블록체인, 비밀번호, 전자서명, 전자투표, 전자상거래 등이 있다.
- 해시함수 알고리즘의 종류에는 대표적으로 SHA, MD5 등이 있다.
