해시 데이터 구조

출처 : 위키백과, 해시테이블

해시 테이블 

• 키와 값으로 구성된 검색 시스템. 모든 키에 대응하는 값이 있다.
• 요소를 검색할 때 시간 복잡도가 O(I)이다.
• 해시 충돌 
• 해시값과 배열 크기 때문에 서로 다른 입력2개가 같은 해시값을 생성할 때 발생
• 발생을 방지하기 위해 '체이닝(chaining)'방식으로 해시테이블을 구현한다.

체이닝(Chaining)

• 요소를 단순한 배열이 아닌 연결 리스트인 배열에 저장하는 방식.
• 즉, 해시 함수가 여러 요소에 대해 똑같은 인덱스를 반환할 경우, 해시값과 해당요소들을 함께 연결하여 해시테이블의 같은 인덱스에 저장한다.
• 연결리스트가 길어졌을 때 테이블 검색의 시간복잡도가 증가할 수 있다.

☞  해싱은 컴퓨터 보안 영역에서 주로 사용된다.

• 디지털 서명이나 사용자 인증 등에 사용된다.
• 양방향(암호화, 복호화)인 암호화와 달리 해싱은 단방향 과정이다.
• 단방향의 1대1함수이므로 비밀번호를 사용하는 보안에 적합하다.(비밀번호 생성 시 DB에 해시값으로 저장)

 

 

 

참고1 : <코드없는 알고리즘과 데이터구조>

참고2 : https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해