追加した順序での列挙
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/08/22 14:07 UTC 版)
「ハッシュテーブル」の記事における「追加した順序での列挙」の解説
追加した順序で要素を列挙する実装方法として、各エントリに追加順を保持するリンクリストのポインタを別に持たせ、列挙する際はそちらのポインタをたどる方法がある。検索・追加操作のみならば単方向リストで実現可能だが、削除操作もサポートする場合は双方向リストで実装しなければO(1)での操作を実現できない。JavaのLinkedHashMapはこの実装であり、その他言語でも利便性からハッシュテーブルが標準で追加順を保証している事がある。欠点として、各エントリに別のリンクリスト用ポインタが必要なためにメモリ消費量が増加する。
※この「追加した順序での列挙」の解説は、「ハッシュテーブル」の解説の一部です。
「追加した順序での列挙」を含む「ハッシュテーブル」の記事については、「ハッシュテーブル」の概要を参照ください。
- 追加した順序での列挙のページへのリンク