1. 해시(Hash) 정의
- 배열은 검색 속도가 빠르나 데이터 삽입/삭제 시 속도가 느립니다.
- 링크드 리스트는 삽입 삭제시 인근 노드의 참조 값만 수정해서 속도가 빠르나 순회 검색만 가능하여 데이터가 많아질수록 속도가 느려집니다.
- 이러한 한계를 극복하기 위해 제시된 방법이 해시(Hash)입니다.
2. 특징
- 내부적으로 배열을 사용하여 데이터를 저장하여 검색 속도가 빠릅니다.
- 데이터의 삽입/삭제 시 해시 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 인덱스로 사용합니다.
- 해시가 내부적으로 사용하는 배열을 Hash Table 이라고 하며 크기에 따라서 성능 차이가 납니다.
3. 해시 메서드(Hash Method)
- 해시는 Hash Table을 사용하여 데이터를 저장합니다.
- 이때 인덱스를 구하기 위해 해시 메서드(Hash Method)를 사용하여 고유의 숫자 값인 해시 코드(Hash Code)를 얻습니다.
4. 해시 메서드 구현 방법
- 해시 메서드는 나머지 연산자를 이용하여 해시 코드(Hash Code)를 구합니다.
* a=97, b=98, c=99 일때Hash Table의 크기가 10이면 다음과 같이 저장됩니다.
97 % 10 = 7
98 % 10 = 8
99 % 10 = 9
list[7] = 'a';
list[8] = 'b';
list[9] = 'c';
5. 해시 충돌
- 해시 충돌을 최소하 하기 위해서 테이블의 크기를 소수로 사용해서 만듭니다.
* 4 % 11 = 4
8 % 11 = 8
32 % 11 = 10 충돌!
10 % 11 = 10 충돌!
- 이러한 충돌을 해결하는 방법은 개방 주소법과 분리 연결법이 있습니다.
6. 개방 주소법
- 배열만을 사용하며, 저장 인덱스가 겹칠 경우 해당 인덱스의 옆 인덱스에 저장하는 방식입니다.
- 옆에 인덱스와 데이터 충돌이 일어나면 다시 옆 인덱스에 저장합니다.
- 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생합니다.
7. 분리 연결법
- Hash Table 에 연결 리스트에서 사용하는 Node 객체를 저장합니다.
- Hash Table의 셀마다 연결 리스트를 하나씩 저장하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드에 추가합니다.
- 데이터를 검색할 때는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 Hash Code와 저장된 Node의 Hash Code를 비교하는 것입니다.
'개발' 카테고리의 다른 글
톰캣에서 HTTP Method 설정하기 (0) | 2020.08.16 |
---|---|
리눅스에서 apache + tomcat 연동 방법 (0) | 2020.08.16 |
JVM 메모리 구조 및 JVM 튜닝 (0) | 2020.08.13 |
Centos7 jdk 1.8 설치 (0) | 2020.08.10 |
리눅스 mysql(5.5.9) 설치 방법 (0) | 2020.08.08 |