해시코드, 해시테이블

해시코드는 객체를 식별할 수 있는 32비트 정수 값을 말한다. (단방향 암호화) 

 

단방향 암호화 
해싱 알고리즘에 의해서 어떤 값이 나왔다면 이 값은 원래대로 복원할 수 없다.

 

해싱 알고리즘 

  1. MD5 (Message Digess Algorithm 5)

• 임의의 길이 값을 받아서 128비트 해시 값을 생성한다.
• 빠르지만 충돌이 쉽게 발생한다는 단점이 있다. 

 2. SHA -1 

• 임의의 길이의 입력 데이터를 160비트의 출력데이터로 바꾸는 알고리즘이다. 
• 인터넷 보안 프로토콜과 공개키 인증서 등에서 적용하고 있는 알고리즘이다. 

객체들은 해싱화된 값 해시코드를 갖고 있다. 
어느 두 객체끼리 비교할 때 이 해시코드를 검사하는데 이 값이 같다면 서로 같은 객체로 본다. 

 

 

해시 테이블 (Hash Table)

•  key-value 쌍에서 key 값을 테이블에 저장할 때, key 값을 해시 함수를 사용해 계산한 후, 그 결과를 배열의 인덱스에 저장하는 자료 구조이다. 
•  저장, 삭제, 검색의 시간 복잡도는 O(1)이다. 

 

 Direct-Address Table 

• 배열을 사용하여 각 키를 배열의 인덱스로 환산해서 데이터에 직접 접근하는 방식이다.  
• 키의 범위가 작고 고유할 때 효율적이다.
• 배열의 크기는 키의 최대값에 따라 결정된다.

 

 

 

해싱 충돌 

  해싱 알고리즘에 의해서 나온 해시코드가 같은 값이 나온다면 이를 '해싱 충돌'이라고 한다. 

 

해싱 충돌 해결 방법

 

1. Chainng - 충돌 시 연결 리스트에 추가하는 방법

 중복된 해시를 연결리스트로 관리하는 방법이다. 

  이 방법은 최악의 경우 수행 시간이 O(n)이 된다. 해시를 사용하는 이유는 O(1)이라는 장점으로 사용하는 것인데 O(n)이 된다면 문제가 된다.

 이런 문제로 트리로 구성하여 더 시간 복잡도를 줄일 수도 있다. 대신 트리는 메모리 사용량이 늘어난다. 

 

 

2.  Open Addressing - 충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간에 데이터를 저장한다. 

- Linear Probing - 충돌한 해시 주소 공간 다음 주소에 할당한다.

- Qaudratic Probing - 충돌한 해시 주소의 제곱 수 만큼 옮겨가서 할당한다. 

- Dobule Hashing - 충돌이 일어 났을 때 다른 해시 함수를 한 번 더 적용하여  할당한다. 

 

 

 

 

 

 

 

 

 

 

 

 

참고 사이트 

https://www.geeksforgeeks.org/direct-address-table/

Direct Address Table - GeeksforGeeks

 

https://ryu-e.tistory.com/87