ハッシュテーブル(連想配列)が、キーのリストと値のリストを返すような実装の時、これらの位置が対応関係

Question

ハッシュテーブル(連想配列)が、キーのリストと値のリストを返すような実装の時、これらの位置が対応関係にないことは有り得るのですか？あるとしてどのような事情があるのでしょうか？

kmee · Accepted Answer

何が言いたいのかがよくわかりませんが
こういうことかなぁ、と疑似言語っぽく書いてみました。

# キーのリスト
keys = hash.GetKeys()
# 値のリスト
values = hash.GetValues()

# 位置が対応関係に「ある」
全てのiについて
hash[keys[i]] == values[i]
が保証されている

# 位置が対応関係に「ない」
ある iについて
hash[keys[i]] == values[i]
とは限らない

こういうことですか?
それでしたら
(1) そのような実装になっているものに心当りはない。が無いとは言い切れない。
(2) 位置の対応が必須なら、私なら他の確実な手段を使う。
・keysを hash.GetKeys() で受けとったら、valuesはhashと keysを使って同じ順番になるように作る。
・「キーと値のセット」のリストがあれば使う。
keyValues = hash.GetKeyValuePairs()

tknakamuri · Answer

>貴方の考えではどうやってキーや値のリストを返せるのですか？
>それと、「〇〇そうとか〇〇と思う」じゃなくて
>事実を教えて欲しいのですが。

うわ、突っかかってきた。それはアルゴリズムの本で勉強したら？

そもそもハッシュというのは検索のためのデータ構造とアルゴリズムで
キーや値の一覧を返すというのは埒外。どう実装しようが「自由」なんですよ。
そこを理解できていないようではどうしようもない。

今でこそハッシュが言語のライブラリに含まれているのは普通だけど
昔は自分で実装するのが普通だったんで、私もいろいろな言語で
いろいろなハッシュの実装をたくさん書きました。
その経験から述べているだけなんだけど・・・

自分の拙い主張以外に聞く耳持たないというならしかたないですね。

Tacosan · Answer

例えばだけど
・「キーのリスト」はキーを「昇順に並べたもの」を返す
・「値のリスト」は値を「挿入した順に並べたもの」を返す
という実装が＊あってはいけない＊という理由, あります?

そもそもとして「ハッシュテーブル」と「連想配列」が根本的に違うものである, という認識をもってもらいたいものではあるが....

tknakamuri · Answer

>あるとしたらどのような事情からそうなっているのか

オープンハッシュだと値の一覧はハッシュ値順とか実装が軽そう。

一方、キーの一覧は登録順の人気が高いと思います。

pythonのdictのkeys()、values()のイテレート順も、同じ並び順になるっぽいけど、ドキュメントには何も書いて無いですね。
同じと仮定するのは危険だと思います。

cametan_42 · Answer

んん〜、#4氏の言ってるような事なのかなぁ。
そもそもやっぱ「キーのリストと値のリストを返すような実装」ってのがどういう意味なのか、って事なんだけど、#4氏の言ってるような事だとすれば、別にハッシュテーブル自体に「キーを全部返す」機能がある、とか「値を全部返す」機能がある、とか言うのって傍流でハッシュテーブルの機能の本懐じゃないよね。
#5氏が指摘してるのは多分そういう事だし。

C言語だっけ?得意なのは。
例えば・・・ええと、GLib使って#4氏が言ってるような事を試してみる、とだ。

GLib:
https://docs.gtk.org/glib/index.html

多分こういうコードになるだろう。

実装例:
https://www.ideone.com/GeJEUC

あんまC得意じゃないんだけど、多分こうなると思う。恐らく。うん。

注: /* WindowsでのMicrosoft処理系でもGLibは使える筈だ、って話は聞くけど詳細は知らん。
Linuxだと、例えばDebian系Ubuntu系列だと、gccとpkg-configを使って

gcc foo.c $(pkg-config --cflags --libs glib-2.0)

みたいにしてコンパイルする。 */

んで結果、

TRUE               
TRUE
TRUE
TRUE
TRUE

みたいな出力になるのね。要はキーと値の「順序」は同じだ、と言う事。

まぁ、GLibみてぇなメジャーなライブラリがそうだったから、って言って他もそうしてるかは知らんけどね。
取り敢えずCで有名なGLibのハッシュテーブルだったらそうだったよ、って話。

っつーか、「違う」って実装なり言語なり知りたいな。どれをどのように想定してんだろ。

tknakamuri · Answer

有り得るでしょう。その方がハッシュの実装が楽ですから。
そもそもハッシュがキーや値のリスト返却の機能を提供するとは限りませんし、提供しても並び順に関する規定はなく、並び順は任意で実装次第です。

cametan_42 · Answer

> ハッシュテーブル(連想配列)が、キーのリストと値のリストを返すような実装

へぇ、そんなのあるの?
どの実装、っつーかどの言語だろう。
こういうカンジの想定?
(注: 利用するプログラミング言語はLisp系のRacket
https://racket-lang.org
とする)

実装例:
https://www.ideone.com/qSLwdV

もちろん、全然ハッシュテーブルって言う程豪華な実装でも何でもないんだけど、想定してる連想配列の挙動、ってこんなカンジかしらん?

> (define *data* '((key1 val1) (key2 val2) (key3 val3) (key4 val4) (key5 val5))) ;;; 連想配列を定義
> (psedo-hash-ref 'key2 *data*)
'(key2 key3 key4 key5)
'(val2 val3 val4 val5)
> (psedo-hash-ref 'key3 *data*)
'(key3 key4 key5)
'(val3 val4 val5)
>

キーのリストと値のリストを「多値として」返す、って言うとこういう挙動かしらん・・・・・・。

真っ向勝負として言うと、keyの位置とvalの位置の対応関係は保持してないと意味が無くなるんじゃないかな・・・・・・。
そもそもハッシュテーブルってキーと値のペアをどう格納すっか、ってのが発想の根幹だろうから、バラバラにする、とかあまり意味が無いように思うんだけど・・・・・・。
はて。

Tacosan · Answer

「これらの位置が対応関係にない」とはどういうことでしょうか? 具体例をお願いします.

そして, あなたは「対応関係にない」ことはありえない, と思っているんだよね? その根拠は?

lv4u · Answer

ハッシュテーブル(連想配列)を実現しているルーチンのアルゴリズムによって、位置関係に意味がある場合と、無い場合があると思います。

ハッシュテーブル(連想配列)が、キーのリストと値のリストを返すような実装の時、これらの位置が対応関係

何が言いたいのかがよくわかりませんが

>貴方の考えではどうやってキーや値のリストを返せるのですか？

例えばだけど

>あるとしたらどのような事情からそうなっているのか

んん〜、#4氏の言ってるような事なのかなぁ。

有り得るでしょう。