자료구조(2)_Hash Table

해시 테이블 ? 

- 해시 함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다. 

- 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다. 

- Java의 Map이 해시 테이블의 대표적인 예다. 

 

해시 테이블 특징 

- 해시 테이블은 순서없이 Key 와 Value로만 값을 저장하기 때문에 순서가 필요한 데이터에는 적합하지 않다. 

- 해시 테이블은 다른 자료구조에 비해 빠른 속도로 삽입, 삭제, 조회가 가능하다.

Key , Value의 형태를 가진다. key는 중복할 수 없지만 값은 중복될 수 있다.

해시 테이블의 구성

Hash

- Hash란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행된다. 

- 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 한 쌍으로 존재하고, Key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1) 이다. 

- Key를 Hash function의 input으로 실행 했을 때 나오는 output.

 

Hash Funtion

- 해시 함수는 키에 대한 해시값을 만드는 함수로 , 키에 대한 해시값을 구하는 과정을 Hashing이라고 한다. 이때 사용하는 함수를 해시함수라고 한다.  즉, 해시함수는 해시를 만드는 함수이다.

- 나눗셈법(Division Method)과 곱셈법(Multiplication Method)이 대표적이다. (충돌해결 방법)

- 입력값 상관없이 고정된 길이의 해시값을 출력한다.

- 복호화가 불가능하다 (단방향 암호화 기법의 특징 )

- 입력값이 일부만 변경되어도 전혀 다른 값을 출력한다. 이 말은 즉, 메시지의 오류나 변조를 탐지할 수 있는 무결성이다. 

대표적인 예로는 블록체인, 비밀번호, 전자서명, 전자투표, 전자상거래 등이 있다.

- 해시함수 알고리즘의 종류에는 대표적으로 SHA, MD5 등이 있다.

해싱되는 과정(key -> HashFunction -> Value )