Chapter 3. Separate Chaining Hashing (2)

동일한 해시 값을 갖는 원소들을 리스트로 연결

 M: 주소 공간, N: 원소의 수 -> M < N
 h(key): 0 ~ M – 1 사이의 정수 i로 매핑
 삽입: i번째 리스트의 제일 앞에 추가 (존재하지 않는 키의 경우)
 검색: i번째 리스트만 검사

기본 개념

 동일한 해시 값을 갖는 원소들은 SequentialSearchST로 구현

구현 방법

 M 개의 배열을 준비
 각 배열은 SequentialSearchST의 참조를 저장
 get()과 put() 등의 함수는 SequentialSearchST의 get()과 put()을 이용하여구현

순서화 연산은 지원되지 않음

public class SeparateChainingHashST<K,V> {
		private int N; // 테이블에 입력된 원소의 수
		private int M; // 해시 테이블의 크기
		private SequentialSearchST<K,V>[] st; // 순차 연결 리스트의 배열로 테이블 구성
    
		public SeparateChainingHashST() { this(997); } // default: 소수
		public SeparateChainingHashST(int M) { // M을 입력받는 생성자
		this.M = M;
		st = (SequentialSearchST<K,V>[]) new SequentialSearchST[M];
		for (int i = 0; i < M; i++)
		st[i] = new SequentialSearchST<K,V>();
	}

	public boolean contains(K key) { return get(key) != null; }
	public boolean isEmpty() { return N == 0; }
	public int size() { return N; }
	// 해시 함수: M으로 나머지 연산
	private int hash(K key) { return (key.hashCode() & 0x7fffffff) % M; }

	public V get(K key) { return st[hash(key)].get(key); } // 리스트를 검색
	public void put(K key, V value) { // 리스트에 추가
		if (!contains(key)) N++;
		st[hash(key)].put(key, value);
	}
	public void delete(K key) { // 리스트에서 삭제
		if (!contains(key)) return;
		st[hash(key)].delete(key); N--;
	}
	public Iterable<K> keys() { // 각 리스트의 원소들을 모두 포함
		ArrayList<K> keyList = new ArrayList<K>(N);
		for (int i = 0; i < M; i++)
		for (K key : st[i].keys())
		keyList.add(key);
		return keyList;
	}
}