(クラス)
有効なハッシュ関数を使って中間サイズのテーブルを最速で検索可能なハッシュ テーブル。
tk: ハッシュ テーブル内のキーのデータ型。
te: ハッシュ テーブル内の要素のデータ型。
table-entry-type: バケットのデータ型を指定します。これは次の指定の型のパブリックなフィールド (またはゲッター/セッターのペア) を持つクラスを指定する必要があります。
- key:tk
- element:te
- next:#table-entry-type
クラスは次のパブリックなゲッターを定義する必要もあります。
- {getter public {valid?}:bool ...}。
バケットのエントリが有効な場合は
true を返します。
エントリが常に有効であれば、最適な動作のために
table-entry-type は
ValidBucketHashTableEntry を継承する必要があります。
key-hash-proc: キーのハッシュ値を返すプロシージャ。このプロシージャには、ハッシュ テーブルのキーと同じデータ型 (
tk) を持つ 1 つのパラメータを指定できます。このプロシージャは
int を返します。
key-hash-proc と
key-equality-proc には、相互に一貫性のある意味を持たせる必要があります。2 つのキーに対する
key-equality-proc への呼び出しが
true を返す場合、2 つのキーそれぞれに対する
key-hash-proc への呼び出しで、同じハッシュ値が生成される必要があります。
key-hash-proc の既定値は
value-hash です。
key-equality-proc: 2 つのキーが等しいかどうかを判定するプロシージャ。このプロシージャにはハッシュ テーブルのキーと同じデータ型 (
tk) を持つ 2 つのパラメータを指定できます。このプロシージャは
bool を返します。2 つのキーが等しい場合、このプロシージャは
true を返します。それ以外の場合、
false を返します。
key-hash-proc と
key-equality-proc には、相互に一貫性のある意味を持たせる必要があります。2 つのキーに対する
key-equality-proc への呼び出しが
true を返す場合、2 つのキーそれぞれに対する
key-hash-proc への呼び出しは、同じハッシュ値を生成する必要があります。
key-equality-proc の既定値は
equal? です。
説明
このテーブルは単純なバケット ハッシュを使用しており、要素が追加されたときにメモリを割り当てます。テーブル サイズが大きくなると、そのローカリティは低下します。このテーブルは、バケット番号としてキーハッシュの下位ビットを使用するため、適切でないハッシュ関数を使用するとパフォーマンスが低下します。大規模なテーブルを扱う場合や予測できないハッシュ関数を使用しなければならない場合は、
HashTable-of を使用するようにしてください。このテーブルは、75% 使用されると、再ハッシュされます。
注意事項
同じキー値を持つ複数のエントリを含めた場合、最後のエントリはハッシュ テーブルに格納されます。
注意事項
コレクションを反復処理中にコレクションの内容を変更することは出来ません。
注意事項
table-entry-type はまれにしか指定されません。指定する 1 つの理由は、もう他から参照されない値にガーベッジ コレクションを実行するテーブルを作成するためです (
Memoizer-of と同様)。例 :
{define-class public WeakBucket
field public key:Object = {uninitialized-value-for-type Object}
field public weak element:#Object
field public next:#WeakBucket
|| Return true if this entry should be kept. Return
|| false if element has been collected, rendering
|| this entry useless.
||
{getter public {valid?}:bool
{return self.element != null}
}
}
{let constant WeakBucketHashTable:Type =
{BucketHashTable-of
Object,
#Object,
table-entry-type = WeakBucket
}
}
コンストラクタ public | {BucketHashTable-of.clone-from from:{BucketHashTable-of
tk,
te,
table-entry-type = table-entry-type,
key-hash-proc = key-hash-proc,
key-equality-proc = key-equality-proc
} } |
コンストラクタ public | {BucketHashTable-of.default efficient-size:int = 4, ...:any} |
アクセサ public BucketHashTable-of.efficient-size:
int セッター public BucketHashTable-of.efficient-size:
int
アクセサ public BucketHashTable-of.size:
int
public | {BucketHashTable-of.clear}:void |
public | {BucketHashTable-of.clone }:{BucketHashTable-of
tk,
te,
table-entry-type = table-entry-type,
key-hash-proc = key-hash-proc,
key-equality-proc = key-equality-proc
} |
filter: | フィルタ操作内で要素を使って要素自体をフィルタリングします。 |
public | {BucketHashTable-of.filter-keys}:void |
public | {BucketHashTable-of.get-if-exists key:tk
}:(value:te, found?:bool) |
public | {BucketHashTable-of.get-key-if-exists key:tk
}:(key:tk, found?:bool) |
public | {BucketHashTable-of.key-exists? key:tk}:bool |
public | {BucketHashTable-of.keys-to-Iterator}:{Iterator-of tk} |
public | {BucketHashTable-of.object-serialize}:void |
public | {BucketHashTable-of.reclaim-invalid-entries}:void |
rehash: | Self-public インターフェイスを再ハッシュします。 |
public | {BucketHashTable-of.rehash}:void |
public | {BucketHashTable-of.remove key:tk,length:int = 1,error-if-missing?:bool = true }:void |
public | {BucketHashTable-of.set key:tk, element:te}:void |
public | {BucketHashTable-of.to-Iterator}:{Iterator-of te} |
(コンストラクタ)
public | {BucketHashTable-of.clone-from from:{BucketHashTable-of
tk,
te,
table-entry-type = table-entry-type,
key-hash-proc = key-hash-proc,
key-equality-proc = key-equality-proc
} } |
BucketHashTable を初期化します。
from: self の初期キーと値のペアを from からコピーします。
(コンストラクタ)
public | {BucketHashTable-of.default efficient-size:int = 4, ...:any} |
BucketHashTable を初期化します。
efficient-size: self の内部テーブルの推奨初期サイズ。この値はより大きな値に合わせて調整されます。
...: 残余引数は、初期キーと要素のペア (2 つずつ渡される) です。
注意事項
同じキー値を持つ複数のエントリを含めた場合、最後のエントリだけはハッシュ テーブルに格納されます。そのキー値を持つ他のエントリは、破棄されます。
(コンストラクタ)
この項目はサポートされていません。内部使用限定となっています。
(アクセサ)
アクセサ public BucketHashTable-of.efficient-size:
int セッター public BucketHashTable-of.efficient-size:
int self の efficient-size を取得または設定します。
説明
(アクセサ)
アクセサ public BucketHashTable-of.size:
int コレクションの要素数を返します。
戻り値
self の要素数を示すint。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| String keys and int elements.
let price:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 56,
"banana", 87,
"cherry", 34
}
|| Display a message indicating the size of
|| the hash table.
{text There are {value price.size} elements in
the hash table.}
}
| |
注意事項
(メソッド)
public | {BucketHashTable-of.clear}:void |
すべての要素を削除します。
説明
このメソッドは、コレクションを反復処理することで、一度に 1 つの要素を削除します。
Association-ofをサブクラス化すると、このメソッドをオーバーライドし、効率的な実装が可能になります。たとえば、コレクションに書き込み可能な
size プロパティがある場合、要素を反復処理するよりも
size をリセットする方が効率的です。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| int keys and String elements.
let my-table:{HashTable-of int, String} =
{new {HashTable-of int, String},
162094, "tom",
439853, "dick",
098627, "harry"
}
|| Clear the hash table.
{my-table.clear}
|| Check if the hash table is empty.
{text The assertion that the hash table is empty is...
{value my-table.empty?}}
}
| |
(メソッド)
public | {BucketHashTable-of.clone }:{BucketHashTable-of
tk,
te,
table-entry-type = table-entry-type,
key-hash-proc = key-hash-proc,
key-equality-proc = key-equality-proc
} |
コレクションのクローンを返します。
戻り値
説明
クローンは、self と同じデータ型を持つ新しいオブジェクトです。クローンには、self の要素の簡易コピー(shallow copy) が含まれます。つまり、どちらかのコレクションの要素に新しいオブジェクトを代入すると、もう一方の一致した要素は元のオブジェクトを参照します。ただし、要素のオブジェクトを変更すると、両方のコレクションは変更したオブジェクトを参照します。
例
例 |
|
{value
|| Declare and initialize set-1 (the original set).
let set-1:{Set-of String} =
{new {Set-of String}, "apple", "banana", "cherry"}
|| Initialize set-2 with a clone of the contents of
|| set-1.
let set-2:{Set-of String} = {set-1.clone}
|| Use a VBox to display the contents of set-2.
|| Iterate over the contents of set-2, adding them
|| to the VBox. Then display the VBox.
let message:VBox = {VBox}
{for each-element:String in set-2 do
{message.add each-element}
}
message
}
| |
注意事項
注意事項
クローンの詳細については、『Curl 開発者ガイド』の「
コレクション」で、使用しているコレクションのクローンに関するセクションを参照してください。
(メソッド)
フィルタ操作内で要素を使って要素自体をフィルタリングします。
p: 要素をフィルタリングするプロシージャ。このメソッドは、self の各要素に対して p を呼び出します。プロシージャには、self の要素と同じデータ型を持つ 1 つの引数を指定する必要があります。プロシージャは、このメソッドが要素をフィルタリングするかどうかを示す bool 値を返す必要があります。p が false を返す場合、このメソッドは self からその要素をフィルタリング (削除) します。p が true を返す場合、要素は、self 内に残ります。
戻り値
このメソッドは値を返しません。
説明
p への呼び出しが false を返すコレクションの要素を削除します。
例
次の例では、ハッシュ テーブルから要素をフィルタリングします。
例 |
|
{value
|| Declare and initialize a hash table with
|| int keys and String elements.
let my-table:{HashTable-of int, String} =
{new {HashTable-of int, String},
162094, "tom",
439853, "dick",
098627, "harry"
}
|| Filter elements that begin with the
|| letter 'd'.
{my-table.filter
{proc {str:String}:bool
{return str[0] != 'd'}
}
}
|| Use a VBox to display the contents of my-table.
|| Add each element to the VBox and then display it.
let message:VBox = {VBox}
{for each-element:String in my-table do
{message.add each-element}
}
message
|| Note that the order of the elements in a hash
|| table is arbitrary.
}
| |
(メソッド)
public | {BucketHashTable-of.filter-keys}:void |
フィルタ操作でキーを使って要素をフィルタリングします。
p: 要素をフィルタリングするプロシージャ。このメソッドは、self の各キーに対して p を呼び出します。プロシージャには、self のキーと同じデータ型を持つ 1 つの引数を指定する必要があります。プロシージャは、関連付けられた要素をこのメソッドがフィルタリングするかどうかを示す bool 値を返す必要があります。p が false を返す場合、このメソッドは self からその要素をフィルタリング (削除) します。p が true を返す場合、要素は、self 内に残ります。
説明
関連付けられたキーを持つ p への呼び出しが false を返す self の要素を削除します。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| String keys and int elements.
let quantity:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 3,
"banana", 0,
"cherry", 8
}
|| Filter elements whose keys begin with 'a'.
{quantity.filter-keys
{proc {str:String}:bool
{return str[0] != 'a'}
}
}
|| Use a VBox to display the contents of quantity.
|| For each key in quantity, add the key to the VBox.
|| Then display the VBox.
let message:VBox = {VBox}
{for key each-element:String in quantity do
{message.add each-element}
}
message
|| Note that the order of the elements in a hash
|| table is arbitrary.
}
| |
(メソッド)
public | {BucketHashTable-of.get-if-exists key:tk
}:(value:te, found?:bool) |
key でインデックス付けされた要素と、示された要素が見つかったかどうかを示すブール値を返します。
key: 取得する要素のキーの値。
戻り値
このメソッドは次の 2 つの値を返します。
- 最初に返される値は、key でインデックス付けされた要素です。
- 2 番目に返される値は、特定の key を持つオブジェクトが self 内に存在するかどうかを示すブール値です。
2 番目に返される値が
false の場合、最初に返される値は不確定です。
(メソッド)
public | {BucketHashTable-of.get-key-if-exists key:tk
}:(key:tk, found?:bool) |
特定のキーと、示された要素が見つかったかどうかを示すブール値を返します。
key: 取得するキーの値。
戻り値
指定されたキーに等しいコンテナが使用しているキー。戻り値は、self のキーと同じデータ型を持ちます。また、キーが見つかったかどうかを示すフラグを返します。
説明
key パラメータが
self 内のキーの場合、そのキーを返します。この場合、2 番目に返される値は
true になります。それ以外の場合、返される値は定義されず、2 番目に戻される値は
false になります。
例
例 |
|
|| Declare and initialize a hash table with
|| String keys and int elements.
{let price:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 56,
"banana", 87,
"cherry", 34
}
}
|| Use the get-key-if-exists method to check for the
|| presence of keys.
The hash table contains prices for...
{price.get-key-if-exists "apple"}
{price.get-key-if-exists "banana"}
{price.get-key-if-exists "pear"}
{price.get-key-if-exists "cherry"}
{price.get-key-if-exists "orange"}
| |
注意事項
このメソッドは、Association-ofで実装されます。Association-of のいくつかのサブクラス内でオーバーライドされます。
(メソッド)
public | {BucketHashTable-of.key-exists? key:tk}:bool |
キーが存在するかどうかを調べます。
key: 調べるキーの値。値は、self のキーと同じデータ型を持つ必要があります。
戻り値
bool 値。値が self のキーである場合、このメソッドは true を返します。それ以外の場合は、false を返します。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| String keys and int elements.
let price:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 56,
"banana", 87,
"cherry", 34
}
|| Check if there is an element with the
|| key "banana" in the collection "price".
{if {price.key-exists? "banana"} then
{text It is there!}
else
{text It is not there.}
}
}
| |
(メソッド)
public | {BucketHashTable-of.keys-to-Iterator}:{Iterator-of tk} |
コレクションの各キーを含む Iterator-of を返します。
戻り値
説明
例
例 |
|
{value
|| Declare and initialize a hash table with
|| int keys and String elements.
let my-table:{HashTable-of int, String} =
{new {HashTable-of int, String},
162094, "tom",
439853, "dick",
098627, "harry"
}
|| Create an Iterator-of from the set.
let my-iterator:{Iterator-of int} =
{my-table.keys-to-Iterator}
|| Use a VBox to display the contents of my-iterator.
|| Iterate over the contents of my-iterator, adding
|| them to the VBox. Then display the VBox.
let message:VBox = {VBox}
{for each-element:int in my-iterator do
{message.add each-element}
}
message
|| Note that the order of the elements in a hash
|| table is arbitrary.
}
| |
注意事項
for コンテナ ループを使って同じ結果を得ることもできます。ただし、この反復処理メカニズムをオーバーライドすると、予期外の結果が生じる可能性があるので、可能な限り
for ループを使用してください。
注意事項
(メソッド)
public | {BucketHashTable-of.object-serialize}:void |
クラス インスタンスが書き込まれるときに、シリアル化コードで呼び出されます。
説明
このメソッドは、次のステップを順番に実行する必要があります。
注意事項
このメソッドは、シリアル化可能なサブクラスでのみ定義する必要があります。
(メソッド)
public | {BucketHashTable-of.reclaim-invalid-entries}:void |
無効なエントリを回収します。
説明
ハッシュ テーブル全体を見て、
table-entry-type によって定義されている
valid? ゲッターを呼び出すことで検知された無効なエントリを削除します。
table-entry-type が
ValidBucketHashTableEntry のサブクラスの場合、何も行いません。
また、
force? が false で、最後に無効なエントリが除去されてからメモリがガーベッジ コレクトを行っていない場合、何も行いません。ウィーク ポインターの回収以外の何らかの理由でエントリが無効になる場合にのみ force フラグは設定される必要があります。
導入:
バージョン 6.0
(メソッド)
public | {BucketHashTable-of.rehash}:void |
Self-public インターフェイスを再ハッシュします。
(メソッド)
public | {BucketHashTable-of.remove key:tk,length:int = 1,error-if-missing?:bool = true }:void |
要素を削除します。
key: 削除する要素のキーの値。この値は、self のキーと同じデータ型を持つ必要があります。
length: このパラメータを指定するとエラーになります。
length コレクションから削除する連続する要素の数を示す
int。ただし、このメソッドでは、ハッシュ テーブルは順序付けられたコレクションではないので、このパラメータには意味がありません。このパラメータは、順序付けられたコレクションを実装する
Sequence-of のサブクラスにのみ適用されます。
このメソッドでは、
length は既定値の
1 に設定されています。
error-if-missing?: ユーザーが存在しない要素を削除しようとしたときにこのメソッドがエラーを生成するかどうかを示すブール値のフラグ。error-if-missing? を true に設定した場合、存在しない要素を削除しようとするとエラーがスローされます。エラーが発生するとプログラムの実行が停止し、エラー メッセージが表示されます。既定では、error-if-missing? は true です。error-if-missing? が false の場合、このメソッドはエラーを生成しません。error-if-missing? キーワード引数。error-if-missing?を指定するには、メソッド呼び出し内のキーワードに必要な値 (例:error-if-missing?=false) を指定します。
説明
{self.key-exists? key} が true を返す場合、このメソッドは self から適切なキーおよび要素を削除します。
{self.key-exists? key} が false で、 error-if-missing? が true の場合、このメソッドはエラーをスローします。ただし、 error-if-missing? が false の場合、このメソッドは何のアクションも実行しません。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| String keys and int elements.
let price:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 56,
"banana", 87,
"cherry", 34
}
|| Remove the element at key "banana".
{price.remove "banana"}
|| Use a VBox to display the contents of price.
|| For each key in price, add a string to the VBox.
|| The string contains the relevant key and element.
|| Then display the VBox.
let message:VBox = {VBox}
{for key each-element:String in price do
{message.add each-element & " " & {price.get each-element}}
}
message
|| Note that the order of the elements in a hash
|| table is arbitrary.
}
| |
注意事項
これは Association-of の抽象メソッドで、Association-of のサブクラス内で実装されます。
(メソッド)
public | {BucketHashTable-of.set key:tk, element:te}:void |
要素の値を設定します。
key: 設定する要素のキーの値。この値は、self のキーと同じデータ型を持つ必要があります。
element: 要素の値。この値は、selfの要素と同じデータ型を持つ必要があります。
説明
key が self に存在する場合、このメソッドは element に関連付けられた要素の値を変更します。key が self に存在しない場合、このメソッドは新しい要素 (key、element) を self に追加します。
例
例 |
|
{value
|| Declare and initialize a hash table with
|| String keys and int elements.
let price:{HashTable-of String, int} =
{new {HashTable-of String, int},
"apple", 56,
"banana", 87,
"cherry", 34
}
|| Change the element at key "banana".
{price.set "banana", 72}
|| Add an element for "pear".
{price.set "pear", 62}
|| Use a VBox to display the contents of price.
|| For each key in price, add a string to the VBox.
|| The string contains the relevant key and element.
|| Then display the VBox.
let message:VBox = {VBox}
{for key each-element:String in price do
{message.add each-element & " " & {price.get each-element}}
}
message
|| Note that the order of the elements in a hash
|| table is arbitrary.
}
| |
注意事項
これは Association-of の抽象メソッドで、Association-of のサブクラス内で実装されます。
(メソッド)
public | {BucketHashTable-of.to-Iterator}:{Iterator-of te} |
コレクションの各要素を含む Iterator-of を返します。
戻り値
説明
Iterator-of の要素の順序は、コレクション型に依存します。配列などの順序付けられたコレクションの場合、このメソッドはその順序を保存します。ハッシュ テーブルやセットなどの順序づけられていないコレクションの場合、要素の順序は任意に指定できます。
例
例 |
|
{value
|| Create a new set.
let my-set:{Set-of String} =
{new {Set-of String}, "apple", "banana", "cherry"}
|| Create an Iterator-of from the set.
let my-iterator:{Iterator-of String} = {my-set.to-Iterator}
|| Use a VBox to display the contents of my-iterator.
|| Iterate over the contents of my-iterator, adding
|| them to the VBox. Then display the VBox.
let message:VBox = {VBox}
{for each-element:String in my-iterator do
{message.add each-element}
}
message
}
| |
注意事項
for コンテナ ループを使って同じ結果を得ることもできます。ただし、この反復処理メカニズムをオーバーライドすると、予期外の結果が生じる可能性があるので、可能な限り
for ループを使用してください。
注意事項