해시 자료구조
여러 길이의 데이터를 효율적으로 관리하기 위해 해시함수를 통해 일정한 길이의 값으로 매핑하는 것.
해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 검색 속도가 빠름.
1. 해당 원소의 해시 함수를 이용해서 해시값을 얻음
2. 해시값을 주소로 하는 위치에 원소를 저장
3. 저장 후 검색 시에도 원소의 해시값으로 계산해 해당 위치로 이동
해시충돌
데이터가 많아지면 같은 키 값을 갖는 데이터가 생긴다는 것, 특정 키의 버켓에 데이터가 집중 된다는 뜻.
너무 많은 해시 충돌은 해시테이블의 성능을 떨어뜨림.
해시함수를 잘 정의해서 해시 충돌을 최소화 하는 것이 성능 개선에 도움이 됨.
해시함수의 입력값은 무한하지만, 출력값의 가짓수는 유한.
해시함수
임의의 길이의 데이터를 고정된 길이의 해시 값으로 변환하는 함수.
데이터를 고르제 분포된 버킷에 할당하기 위해 사용.
충돌이 적은 해시 함수의 설계
동일한 해시 값을 가진 데이터가 두 개 이상인 경우 충돌이 발생할 수 있음.
- 체이닝
- 해시 충돌이 발생하면 연결리스트를 사용해 중복된 값을 저장. 주로 구현이 간단한 체이닝 방법 사용
- 버켓이 꽉 차더라도 연결리스트로 계속 늘려가므로, 데이터의 주소값은 바뀌지 않음.
- 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적음
- 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생
- 이 경우 최악의 경우 수행 시간이 O(n)이 됨.
- 해시를 사용하는 이유는 O(1)이라는 장점인데 O(n)이된다는 문제 발생.
- 트리로 구성해서 더 시간 복잡도를 줄일 수 있음.
- 개방 주소법
- 인덱스가 중복되었다면 다른 빈 인덱스를 찾아 저장함
- linear probing: 충돌시 빈 slot이 나올 때까지 탐색 후, 가장 가까운 빈 인덱스를 사용
- primary clustering 문제 발생.
- 한 번 충돌이 나면 집중적으로 충돌이 발생하는 것.
- 평균 검색 시간이 증가
- quadratic probing: 2의 제곱수로 탐색하여 빈 인덱스를 사용
- secondary clustering 문제 발생.
- 처음 충돌한 위치가 같다면 앞으로도 발생할 충돌위치도 반복적으로 계속 충돌
- double hashing probing : 빈 인덱스를 찾을 때까지 해시 함수를 사용해서 탐색
- 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없음
- 삽입, 삭제시 오버헤드가 적음
- 저장할 데이터가 적을 때 더 유리
- linear probing: 충돌시 빈 slot이 나올 때까지 탐색 후, 가장 가까운 빈 인덱스를 사용
- 인덱스가 중복되었다면 다른 빈 인덱스를 찾아 저장함
- 동적 해싱
- 해시 테이블의 크기를 동적으로 조절해서 해시 충돌 최소화하고 효율적인 해시 테이블 유지
- 자바는 개별체이닝, 파이썬은 오픈 어드레싱
Double Hashing의 장점과 단점, 해결방안
충돌이 발생한 버킷에 다른 버킷에 데이터를 저장하는 방식.
두 개의 해시 함수를 사용해서 다음 이동 위치를 결정
+장점
- 해시 테이블의 공간 사용을 최소화하고 버킷들 사이의 균형을 맞추어 해시 충돌을 감소시킬 수 있다는 점
- 단점
- 해시 함수의 선택이 중요함
- 연산량이 많음. 캐시의 효율이 좋지 않음
-
군집화(clustering)
- 개방 주소법을 사용하면 해시값이 몰리는 군집화가 발생함.
- 선형조사는 1차 군집화
- 이차, 랜덤 조사는 2,3차 군집화가 발생
- 이중 해싱은 동의어들이 저마다 제 2의 해시함수를 갖고 있기 때문에 점프 시퀀스가 일정하지 않음
- 이중해싱은 군집화의 해결방법
(h(key)+jXd(key))%M, j=0,1,2,3...
기본적인 해시함수 h로 키를 인덱스로 변환하고 두번째 함수 d는 다음 위치를 위한 점프 크키를 규칙에 따라 정함.
d는 점프 크기를 정하는 함수이므로 0을 리턴해서는 안됨.
그리고 d의 해시값과 해시테이블의 크기 M은 서로소 관계일 때 좋은 성능을 만들어냄.
(M을 소수로 선택하면 자연스럽게 만족)
Load Factor(적재율,람다) 자바의 해시 자료구조는 Load Factor 정책
- 로드 팩터
- 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것
- 로드 팩터의 비율에 따라서 해시 함수를 재작성하거나 해시 테이블의 크기를 조정
- 자바 10에서는 해시 맵 디폴트 로트 팩터를 0.75로 정해서 이를 넘는 경우 해시 테이블의 공간을 재할당
자바
jdk 7 까지는 linked list를 사용한 separate chaining 사용, O(N)
jdk 8 에서 linked list와 red black tree를 혼용한 separate chaining 활용
충돌이 적을 떄는 linkedlist, 많을 때는 red black tree로 작동, O(logN)
- linkedlist는 탐색하는데 O(n)이들지만 red-black tree는 O(logN)이 들기 때문에 성능 개선임
- 동일하지 않은 어떤 객체 X와 Y가 있을 때
- 즉, X.equals(Y)가 거짓일 때, X.hashCode() != Y.hashCode()가 같지 않다면
- 이 때 사용하는 해시 함수는 완전한 해시 함수
- Integer, Long, Double같은 Number 객체는 객체가 나타내려는 값 자체를 해시 값으로 사용할 수 있기 때문에 완전한 해시 함수 대상으로 삼을 수 있음.
- 하지만 String 이나 POJO에 대해 완전한 해시 함수를 제작하는 것은 불가능
- 자바는 기본적으로 hashcode() 함수의 리턴값을 int로 지정해놓았기 때문에 2^32개의 객체를 다르게 저장할 수 있지만 가능한 키 범위가 더 많을 수도 있고, 가능한 키 범위와 동일하게 배열의 크기를 할당해 놓는게 아니라 동적으로 늘려가기 때문에 충돌이 발생할 수 밖에 없음.
- 인덱스를 정하는 방법은 int index = X.hasgCode()%M;
- M은 배열의 크기
- 이 식에서 알 수 있는 것은 hashcode의 값이 달랐더라도 M 모듈러 연산을 하면서 한번 더 해쉬충돌이 일어날 수 있어 총 2번의 충돌이 가능하다는 점
멀티스레드 환경에서의 해시 테이블
- Map 인터페이스의 구현체
- HashMap, HashTable, ConcurrentHashMap
- HashMap
- key와 value에 null을 허용
- 동기화를 보장하지 않음
- thread-safe하지 않아 싱글 스레드 환경에서 사용해야함.
- 동기화 처리를 하지 않아서 데이터 탐색 속도가 빠름.
- HashTable과 ConcorrentHashMap보다 데이터를 찾는 속도는 빠르지만, 신뢰성과 안정성이 떨어짐.
- HashTable
- key와 value에 null을 허용하지 않음
- 동기화를 보장
- 멀티 스레드 환경에 사용할 수 있음.
- 데이터를 다루는 get(), put(), remove()등의 메소드에 syncronized 키워드가 붙어 있음.(메소드 전체가 임계구역으로 설정)
- 해당 키워드를 메소드를 호출하기 전에 스레드간 동기화 락을 검
- 멀티 스레드 환경에서 데이터의 무결성 보장.
- 스레드간 동기화 락은 매우 느린 동작이라는 단점
- 객체마다 Lock을 하나씩 다지고 있기 때문에 동시에 여러 작업을 해야할 때 병목현상이 발생.
- ConcurrentHashMap
- key와 value에 null을 허용하지 않음
- 동기화를 보장
- HashMap의 동기화 문제를 보완하기 위해 나타남.
- 동기화 처리를 할 때, 어떤 Entry를 조작하는 경우에 해당 Entry에 대해서만 락을 검.
- HashTable보다 데이터를 다루는 속도가 빠름.
- Entry 아이템 별로 락을 걸어 멀티 스레드 환경에서의 성능을 향상시킴.
- get()에는 syncronized가 없어서 여러 스레드에서 동시에 읽을 수 있음
- put()에는 특정 세그먼트 or 버킷에 Lock을 사용해서 스레드 세이프하게 사용가능
- 버킷 단위로 lock을 사용하기 때문에 같은 버킷만 아니라면 lock을 기다릴 필요가 없음.
- 같은 버킷만 아니라면 여러 쓰레드가 동시에 쓰는 작업을 할 수 있기 때문에
읽기 작업보다 쓰기 작업 성능이 중요한 작업에서 적합 - 읽기 작업은 동기화가 적용되지 않아서 검색직전 가장 최근에 완료된 업데이트 작업의 결과가 반영, 삭제된 게시글을 보려고 누르면 삭제된 게시글입니다 뜨고 끝
- thread-safe 하기 위해 syncronized 키워드를 사용
- 여러개의 스레드가 한개의 자원을 사용하고자 할 떄, 현재 데이터를 사용하고 있는 스레드를 제외하고 나머지 스레드들은 데이터에 접근할 수 없도록 막는 것
- 변수와 함수에 사용해서 동기화 할 수 있음.
- 너무 사용하면 프로그램 성능 저하가 일어남
- 자바 내부적으로 block과 unblock을 처리하게 되어서
