Hash Table

개념

• 키, value를 대응시켜 저장하는 데이터 구조
• 키를 통해 해당 데이터에 빠르게 접근 가능
• 해싱: 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

해시충돌

개념

해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 - 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우

해결방안

1) 개방 주소법

• 충돌 시, 테이블에서 비어 있는 공간에 hash를 찾아 데이터를 저장
• Hash 와 value가 1:1 관계 유지 가능

1-1) 선형탐사법

• 빈공간을 순차적으로 탐사
• 일차 군집화 문제 발생

1-2) 제곱탐사법

• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
• 일차 군집화 문제 해결, 하지만 2차 군집화 문제 발생

1-3)이중해싱(더블해싱)

• 최초 해시를 구할 때 사용
• 충돌 발생 시, 탐사 이동 간격을 구할 때 사용

2) 분리 연결법

• 연결리스트로 구성, 해당 테이블에 데이터 연결
• 1:1 관계가 아님 -> 찾는데 시간이 오래걸릴 수 있다.

사용방법

정의

Hashtable<String, Integer> ht = new Hashtable();
ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);
ht.put("key3", 50);

 for (Map.Entry<String, Integer> item : ht.entrySet()) {
            System.out.println(item.getKey()+" - "+item.getValue());
        }