ハッシュは何のために設定されていますか？

ハッシュセットのデータ構造（および一般に設定される）は非常にまれな構造であるため、すべての標準ライブラリにはありません。 たとえば、.NET Frameworkでは、バージョン3.5でのみ登場しました。 ただし、場合によっては、ハッシュセットが非常に役立つことがあります。



この記事では、ハッシュセットを使用することが理にかなっている場合と、そのために支払う必要があるものを示します。







まず、何が設定されます。 これはそのようなコレクションであり、その要素は無秩序で一意です（つまり、コレクションに1回しか存在しません）。 セットは基本操作をサポートします：

• アイテムを追加します。
• アイテムを削除します。
• アイテムが存在するかどうかを確認します。
• すべての要素を調べます。

セットの実装は、検索に使用されるデータ構造のみが異なります。配列、リスト、ツリー、ハッシュテーブル、またはその他のものを指定できます。 実際には、ハッシュテーブルは合理的なオーバーヘッドで最大のパフォーマンスを提供するため、最もよく使用されます。



次に例を見てみましょう。 タグのリストの等価性に応じて多数の要素のグループ化を実装する必要があり、タグについては無視リストが定義されていると仮定します。つまり、比較に関与すべきではないタグです。 この場合、タグは短い文字列（主に単語）です。 また、無視リストに約100個のタグが含まれているとします。



Rubyでは、アルゴリズムは次のとおりです。

def group_elements(elements, ignore_list) groups = [] for element in elements assigned = false for group in groups #   ,     true; #  ,  false. if group.accept(element, ignore_list) assigned = true break end end #      , #     . if !assigned groups << Group.new(element) end end return groups end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Group :: accept（）メソッドの実装方法は次のとおりです。

 class Group ... def accept(element, ignore_list) for my_element in @elements if my_element.match(element) @elements << element return true end end return false end ... end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最後に、Element :: match（）メソッド：

 class Element ... def match(element, ignore_list) #  . my_tags_filtered = @tags.select { |tag| !ignore_list.include?(tag) } its_tags_filtered = element.tags.select { |tag| !ignore_list.include?(tag) } #  . intersection = my_tags_filtered & its_tags_filtered #        #      . return intersection.length > 0 && intersection.length == [my_tags_filtered.length, its_tags_filtered.length].max end ... end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、額面の実装を示します。タグリスト自体と無視リストの両方が通常の動的配列です。 つまり、ignore_list.include操作ですか？ 線形の複雑さを持っています。 また、タグは平均長が5〜10文字の文字列であり、文字列の比較自体には線形の複雑さがあることを思い出してください。 グループ化がO（n ² ）複雑であることを考慮すると、基本的な比較操作の最適化により、生産性が大幅に向上します。



ハッシュセットは、実装をより最適化するのに役立ちます。 それを使用して無視リストを実装すると、2つの重大な利点が得られます。 まず、リスト内の線形検索を取り除き、ハッシュキー検索に置き換えます。 次に、文字列の比較を取り除きます。 本当に一つの注意点があります-Rubyにはハッシュセットのデータ構造はありません。 ただし、要素がキーとして使用される通常のハッシュテーブルをハッシュセットで置き換えることができるため、これは問題ではありません（可能な限り最小のサイズの任意のタイプを使用できます）。 この奇妙なトリックは、たとえばNHibernateに適用され、それ以上ない場合はうまく機能します。



上記のRubyアルゴリズムの2つの実装を、2000〜3000程度の要素数、2〜15 UTF-8文字のタグサイズ、および平均5の要素ごとのタグ数と比較しました。ハッシュセット配列を置き換えると、約10回。



一般に、ハッシュセットを使用すると、集合に対する操作（交差、結合、減算）をより最適に実装できます。 ただし、それらの冗長性を忘れないでください。 ハッシュセットは、要素を保存するのに必要なメモリよりもはるかに多くのメモリを予約するため、中規模のセット（100〜10000要素）に対してのみ使用するのが理にかなっています。 実際、計算を高速化するためにメモリを浪費しています。 大規模なセットでは、ツリーを使用する必要があります。