10220


ユニティで各アセットを管理するのにハッシュ値を適用しようと考えています。

ファイル名まで含んだフルパスに対してString.GetHashCode()からハッシュ値を  
得ようとしております。

下記、MSDNを見る限り文字列が異なれば必ずハッシュ値が異なるように見えるのですが、  
必ずユニークになるとの記述はないため、このまま使用していいものかわからずにいます。

<https://msdn.microsoft.com/ja-
jp/library/system.string.gethashcode(v=vs.80).aspx>

知見をお持ちの方いらっしゃいましたら教えてください。

Unityなので.Net2.0まで使用可能です。  
Unityバージョンは5.0.1f1

  
【追記】  
やりたいこととしては下記スクールストライクガールズのＰＤＦの74ページ目にある仕組みを作ることです。  
<http://www.jp.square-
enix.com/info/images/image_technical_seminar2014_06/pdf/SQEX_DevCon_sugimoto.pdf>

ファイルの実体を１つのバイナリデータとして保存し、  
下記構造体のリストでファイルパスとオフセット位置とファイルサイズを管理するという  
ファイルシステムを構築するためにファイルパスを可逆なものにしたいと思っています。

[code]

    public struct FileSystemStruct
    {
        public int HashCode;            // アセット名のハッシュコード
        public long OffsetPosition;     // ファイルシステム上のアセットデータの開始位置
        public long Filesize;           // ファイルシステム上のアセットデータのサイズ
    }
    
[/code]

【使い方】  
ＵＩから指定パスのアセットをロードしたいというイベントが発生した時に、  
指定パスをハッシュ化して、構造体のリスト内を検索してヒットした位置の  
バイナリをロードするといった仕組みを構築するつもりです。


CC BY-SA 3.0
2015-05-14T10:13:38.357
10172
2015-05-15T17:36:26.083
2015-05-15T12:48:58.373
5261
5261
question
c# unity3d
String.GetHashCode()は文字列が一致しなければ必ずユニークでしょうか？


`int`型である`GetHashCode()`は2^32通りの値しかありません。  
これ以上の件数(例えば5文字の文字列の全組み合わせ)のハッシュ値をすべて計算すれば必ず衝突が発生します。


CC BY-SA 3.0
2015-05-14T10:28:43.300
10174
2015-05-14T11:35:00.793
2015-05-14T11:35:00.793
8000
5750
10172
answer


いいえ。異なる文字列から同じハッシュコード値を返すことが、メソッド仕様上ありえます。

`String.GetHashCode`メソッドのような「ハッシュ関数」は、一般に以下のような性質をもちます。

  * 同じ入力データに対しては、必ず同じハッシュコード値を返す。
  * 異なる入力データに対しては、 **できる限り異なる** ハッシュコード値を返すよう設計される。
  * 異なる入力データに対して、 **偶然に** 同じハッシュコード値を返すことはあり得る。（衝突）
  * 2つの入力データの差異が小さくても、出力されるハッシュコード値は **なるべく分散** するように設計される。
  * 得られたハッシュコード値から、元の入力データを **復元することはできない** 。（一方向）

また`String.GetHashCode`メソッド固有の問題として、「動作環境が異なる場合、同じ入力データに対して、同じハッシュコード値を算出する保証がない」と明記されています。このメソッド（のデフォルト動作）は、プログラム動作中でのみ利用するハッシュ値専用であり、ファイルシステムのような永続化されるデータ管理に用いるべきではありません。

* * *

> ＵＩから指定パスのアセットをロードしたいというイベントが発生した時に、  
>  指定パスをハッシュ化して、構造体のリスト内を検索してヒットした位置の  
>  バイナリをロードするといった仕組みを構築するつもりです。

目指しているものは、[ハッシュテーブル](http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB)実装のように聞こえます。この場合でも、ハッシュ値の
**衝突** は必ず考慮しなければなりません。

色々と汎用性を考慮して独自実装を進めると、オリジナルファイルシステムの劣化版が出来上がる恐れもあります。どこかで前提条件を割り切るなど、制約を設けることを検討された方が良いと思います。


CC BY-SA 3.0
2015-05-15T08:18:46.453
10220
2015-05-15T08:25:57.727
2015-05-15T08:25:57.727
49
49
10172
answer


スクールストライクガールズのＰＤＦの74ページ目の仕組みはアセット名からハッシュ値を作るよりもアセット名に順にIDを振っていき、アセット名を利用する部分をIDで置換していく方が的確な気がします。  
リソースを統合し、ID情報からランダムアクセス可能にするというのがまず最初の目的になるでしょう。

"UIから指定パスのアセットをロードしたいというイベントが発生した時に、指定パスをハッシュ化する"までやってしまうなら、Dictionaryを利用してアセット名をidに変換する方がシンプルかつ見通しも良いと思います。

第２段階として、変換を0にしてDictionary型を排除することができるか検討する形になると思います。つまり、アセット名のハードコーディングの削除を目指します。


CC BY-SA 3.0
2015-05-15T09:56:16.520
10227
2015-05-15T09:56:16.520
9407
10172
answer


他の方が言われているとおり、int型は、2^32通りのパターンしか表現できないので、衝突が発生します。

短い文字列であっても、衝突の可能性は、あり得ます。  
MD5など他のハッシュアルゴリズムを使用した場合にも完全に回避できません。

衝突を回避する方法として、 **GetHashCode** と併用して、 **Equals** による判定を行います。  
例えば、Dictionaryの内部実装は、GetHashCodeで簡易的な判定を行ったあと、  
Equalsメソッドを呼び出し、オブジェクトの内容が一致するか判定を行っています。

Dictionaryのような型を使用した場合、ハッシュと併用として内容の一致判定まで行うので、衝突について気にする必要は、ありません。


CC BY-SA 3.0
2015-05-15T17:36:26.083
10240
2015-05-15T17:36:26.083
2207
10172
answer