第八章Cachéアルゴリズムとデータ構造の分散リスト

文書ディレクトリ

第八章Cachéアルゴリズムとデータ構造の分散リスト

ハッシュ

完全例

チェーンテーブルノードクラス

ハッシュ表クラス

呼び出し

第八章Cachéアルゴリズムとデータ構造の分散リスト
ハッシュ・リスト
ハッシュ・テーブルとも呼ばれ、このデータ構造はキー値(value)のマッピング関係を提供し、キーを1つ与えるだけで一致するvalueを効率的に検索することができ、時間的複雑さはO(1)に近い.
key
value
key1
vaule1
key2
vaule2
key3
vaule3
key4
vaule4
完全な例
ダイレクトアドレスの場合、キーワードkを有する要素はスロットkに格納される.例えば、キーワードドメインが3,5,9,11の4つの数であれば、3,5,9,11の4つの位置にしか格納されず、他の位置はすべて浪費され、このときハッシュ関数hにより、キーワードドメイン内の要素をハッシュ[0,m−1]の位置にマッピングすることができる.
このとき、メモリのコストが大幅に減少します.
ハッシュ関数は次のように定義されます.
index=key%16;
リンク法によって衝突の問題を解決するには、次の手順に従います.
チェーンテーブルノードクラス

Class PHA.YX.Arithmetic.HashMap.HashEntry Extends %RegisteredObject
{

Property key As %Integer;

Property value [ InitialExpression = 0 ];

Property next As HashEntry;

Property pre As HashEntry;

}

ハッシュ表クラス

Class PHA.YX.Arithmetic.HashMap Extends %RegisteredObject
{

Property size As %Integer [ InitialExpression = 16 ];

Property arrayList As array Of PHA.YX.Arithmetic.HashMap.HashEntry;

Method %OnNew() As %Status [ Private, ServerOnly = 1 ]
{
	f i = 0 : 1 : ..size - 1 d
	.d ..arrayList.SetAt("", i)
	Quit $$$OK
}

Method getContainer() As %ListOfObjects
{
	q ..arrayList
}

Method getIndex(key As %Integer)
{
	q key#16
}

Method insert(key As %Integer, value As %Integer) As %Boolean
{
	q:..get(key)'="" $$$NO
	s index = ..getIndex(key)
	q:index>16 $$$NO
	s ret = $$$NO
	if (..arrayList.GetAt(index) = "") {
		s mEntry = ##class(PHA.YX.Arithmetic.HashMap.HashEntry).%New()
		s mEntry.key = key
		s mEntry.value = value
		d ..arrayList.RemoveAt(index)
		d ..arrayList.SetAt(mEntry,key)
		s ret = $$$YES
	}
	else {
		s mEntry = ..arrayList.GetAt(index)
		s preEntry = mEntry
		while (mEntry '="") {
			s preEntry = mEntry
			s mEntry = mEntry.next 
		}
		s newEntry = ##class(PHA.YX.Arithmetic.HashMap.HashEntry).%New()
		s newEntry.pre = mEntry
		s newEntry.key = key
		s newEntry.value = value
		s preEntry.next = newEntry
		s ret = $$$YES
	}  
	q ret
}

Method get(key As %Integer) As PHA.YX.Arithmetic.HashMap.HashEntry
{
	s index = ..getIndex(key)
	q:..arrayList.GetAt(index)="" ""
	
	s ret = ""
	#dim mEntry as PHA.YX.Arithmetic.HashMap.HashEntry = ..arrayList.GetAt(index)
	while ((mEntry '= "")&&(ret = ""))
	{
		i mEntry.key = key d
		.s ret = mEntry
		e  d
		.s mEntry = mEntry.next
	}
	q ret
}

Method remove(key As %Integer) As %Boolean
{
	s index = ..getIndex(key)
	q:..arrayList.GetAt(index)="" $$$NO
	
	#dim mEntry as PHA.YX.Arithmetic.HashMap.HashEntry = ..arrayList.GetAt(index)
	while (mEntry '= ""){
		if (mEntry.key = key){
			if (mEntry.pre = ""){
				s mEntry.value = ""
				return $$$YES
			}else{
				s mEntry.pre = mEntry.next
				return $$$YES
			}
		}else{
			s mEntry = mEntry.next
		}
	}
	return $$$NO
}

Method edit(key As %Integer, value As %Integer) As %Boolean
{
	#dim mEntry as PHA.YX.Arithmetic.HashMap.HashEntry = ..get(key)
	q:mEntry="" $$$NO
	s mEntry.value = value
	q $$$YES
}

}

よびだし

/// w ##class(PHA.YX.Arithmetic).HashMap()
ClassMethod HashMap()
{
	s $zt = "ErrHashMap"

	#dim mHashMap as PHA.YX.Arithmetic.HashMap = ##class(PHA.YX.Arithmetic.HashMap).%New()
	d mHashMap.insert(1,2)
	d mHashMap.insert(17,3)
	w mHashMap.get(1),!
	w mHashMap.get(17),!
	w mHashMap.get(1).value,!
	w mHashMap.get(17).value,!
	d mHashMap.edit(1,4)
	w mHashMap.get(1).value,!
	w mHashMap.get(17).value,!
	d mHashMap.remove(1)
	w mHashMap.get(1).value,!
	w mHashMap.get(17).value,!
	q ""
ErrHashMap
	q $ze
}

簡単な衝突テストを行い,最後に出力結果を示したが,この2つのアドレスは明らかに異なる.

DHC-APP>w ##class(PHA.YX.Arithmetic).HashMap()
[email protected]
[email protected]
2
3
4
3
 
3