Chapter 3. Separate Chaining Hashing (2)

13062 ワード
アルゴリズム#アルゴリズム# Hashing テキストリンク
同じハッシュ値を持つ要素をリストに接続
M:アドレス空間,N:要素数->M6155 h(キー):0からM–1の間にマッピングされた整数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;
	}
}
DOM要素のカウント
求職:私のユーザー体験の道