HashMap & Hashtable

1699 ワード
テキストリンク

  • シーケンスX,繰返し(キーX,値O)

  • Mapインタフェースを実装します.キー値ペアとしてデータを保存

  • Hashtable:旧バージョン(同期O)

    • HashMap:新バージョン(同期X)


  • Mapインタフェースを実装する典型的な集合クラス

  • 順序を維持するにはLinkedHashMapを使用します

  • ハッシュ技術を用いてデータを格納するため,データが多くても検索速度が速い.

  • key-value pair:keyは繰返しX、valueは繰返しO
    • public class HashMap extends AbstractMap
					implements Map, Cloneable, Serializable {
    transient Entry[] table;	// 배열. Entry = key-value pair
    ...
    static class Entry implements Map.Entry {
    	final Object key;
        Object value;
    }
}

    TreeMap:TreeSetと同じプロパティ(バイナリナビゲーションツリー)


  • 範囲検索とソートに有利な集合クラス

  • HashMapよりもデータの追加/削除時間が長い

    • ハッシュ＃ハッシュ＃


  • エドワード・ブスコースの概要を参照してください

  • key->ハッシュ関数->リターンインデックス(ハッシュコードと呼ばれる格納場所)

  • ハッシュとは?ハッシュ関数を用いて、ハッシュテーブルにデータを格納および読み出します.

  • スケジュールは何ですか.アレイ(Array)とリンクリスト(LinkedList)の組み合わせの形式.
    Hashtable = {LinkedList1, LinkedList2, LinkedList3, LinkedList4 ...};
    アレイの利点「アクセス性」+リンクリストの利点「可変ガラス」=Hashtable

  • HashCode()を使用する関数:HashTable、HashMap、HashSet
    -> Objects.hash()を使用して作成します.

  • HashTableに保存されているデータを取得するプロセス
  • キーでハッシュ関数を呼び出し、ハッシュコード(配列のインデックス)を得る.
  • HashCodeに対応するLinkedListを配列内で検索します.
    • 鍵に一致するデータを
  • LinkedListで検索します.

  • 「同じキー」の場合、ハッシュ関数は「常に同じハッシュコード」を返さなければなりません.
    異なるキーであっても、同じ値のハッシュコードを返すことができる.(同じリンクリストに存在します.)
    • leetcode Pow(x,n)高速べき乗
    コーディングの定理