Java 改良章 (33)-----マップの概要
- 黄舟オリジナル
- 2017-02-11 10:24:081423ブラウズ
前回のLZでは、HashMap、Hashtable、TreeMapの実装方法をデータ構造、実装原理、ソース解析の3つの側面から詳しく説明しました。
： 推奨読書: java改善の章(23) - hashmap
javaの増加の章(25) - -Hashtable
Java改善の章(26)-----hashCode
Java改善の章(27)--TreeMap
1. マップの概要
まず Map の構造図を見てください
Map:
「キーと値」マッピングの抽象インターフェイス。マップには重複キーは含まれておらず、1 つのキーが 1 つの値に対応します。 SortedMap:
Map インターフェースを継承する、順序付けされたキーと値のペアのインターフェース。 NavigableMap:
SortedMap を継承し、指定された検索ターゲットに最も近い一致のナビゲーション メソッドを返すインターフェイスを持ちます。 AbstractMap:
は、Map の関数インターフェイスのほとんどを実装します。 「Map実装クラス」の繰り返しコーディングを軽減します。 Dictionary:
キーを対応する値にマップするクラスの抽象親クラス。現在は Map インターフェイスに置き換えられています。 TreeMap:
順序付けされたハッシュ テーブルは、SortedMap インターフェイスを実装し、最下層は赤黒ツリーを通じて実装されます。 HashMap:
は、「ジッパーメソッド」に基づくハッシュテーブルです。最下層は「配列+リンクリスト」を使って実装されています。 WeakHashMap:
「ジッパーメソッド」に基づくハッシュテーブル。 HashTable:
「ジッパーメソッド」に基づくハッシュテーブル。 要約は次のとおりです:
それらの違い:
2. 内部ハッシュ: ハッシュ マッピング テクノロジー
ほぼすべての一般的なマップはハッシュ マッピング テクノロジーを使用します。私たちプログラマーはそれを理解する必要があります。
ハッシュ マッピング テクノロジーは、要素を配列にマッピングする非常にシンプルなテクノロジーです。ハッシュ マップは配列の結果を使用するため、任意のキーによる配列へのアクセスを決定するためのインデックス付けメカニズムが必要です。このメカニズムをハッシュ関数と呼びます。 Java では、そのような整数を見つけることについて心配する必要はありません。すべてのオブジェクトには整数値を返す hashCode メソッドが必要であり、必要なのはそれを整数に変換し、その値を配列で除算することだけです。サイズから余りを取り出します。以下の通り:
int hashValue = Maths.abs(obj.hashCode()) % size;
以下は HashMap と HashTable です:
----------HashMap------------
//计算hash值
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算key的索引位置
static int indexFor(int h, int length) {
return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length; //确认该key的索引位置位置のインデックスは、配列内のノードの位置を表します。次の図は、ハッシュ マップの基本原理図です:
この図では、ステップ 1 ～ 4 は配列内の要素の位置を見つけること、ステップ 5 ～ 8 は配列内の要素の位置を見つけることです。要素を配列に追加します。挿入プロセス中に少しイライラすることがあります。同じハッシュ値を持つ複数の要素が存在する可能性があるため、それらは同じインデックス位置を取得します。これは、複数の要素が同じ位置にマッピングされることを意味します。このプロセスは「競合」と呼ばれます。競合を解決する方法は、インデックス位置にリンク リストを挿入し、このリンク リストに要素を追加するだけです。もちろん単純な挿入ではなく、インデックス位置のリンクリストを取得し、そうでない場合はその要素を直接挿入します。キーと同じである場合は、元のキーの値を上書きして古い値を返します。それ以外の場合、要素はチェーンの先頭に保存されます (最初に保存された要素はチェーンの最後に配置されます)。 。以下は HashMap の put メソッドで、インデックス位置を計算し、要素を適切な位置に挿入するプロセス全体を詳細に示しています:
public V put(K key, V value) {
//当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode());
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length);
//从i出开始迭代 e,判断是否存在相同的key
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同，则直接覆盖value，返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
} HashMap の put メソッドは、次の基本的な考え方を示しています。実際、他のマップを見ると、原則が似ていることがわかります。
3. マップの最適化
まず第一に、ハッシュマップの内部配列のサイズは 1 のみであり、すべての要素がこの位置 (0) にマッピングされると仮定します。より長いリンクリストを形成します。更新時やアクセス時にはこのリンクリストに対して線形探索を行う必要があるため、必然的に効率が悪くなってしまいます。非常に大きな配列があり、リンクされたリストの各位置に要素が 1 つしかない場合、アクセス時にインデックス値を計算してオブジェクトが取得されると想定します。これにより検索の効率は向上しますが、無駄が生じます。コントロール。確かに、これら 2 つの方法は極端ではありますが、最適化のアイデアを提供します。 要素が均等に分散されるように、より大きな配列を使用します。 Map には効率に影響する 2 つの要素があります。1 つはコンテナーの初期サイズで、もう 1 つは負荷率です。 3.1は、実装サイズを調整します。マップのサイズを調整できるようになります。マップ内の要素が一定量に達すると、コンテナ自体のサイズが変更されることはわかっていますが、このサイズ変更プロセスは非常にコストがかかります。サイズを変更するには、元の要素をすべて新しい配列に挿入する必要があります。インデックス = ハッシュ(キー) % の長さはわかっています。これにより、元の競合しているキーが競合しなくなり、競合していないキーが競合するようになる可能性があります。再計算、調整、挿入のプロセスは非常にコストがかかり、非効率的です。したがって、マップの予想されるサイズ値を把握し始めて、マップのサイズを十分に大きくすると、サイズ変更の必要性を大幅に削減、または排除することができ、速度が向上する可能性が高くなります。
以下は、HashMap がコンテナー サイズを調整するプロセスです。次のコードを通して、その拡張プロセスの複雑さを確認できます。void resize(int newCapacity) {
Entry[] oldTable = table; //原始容器
int oldCapacity = oldTable.length; //原始容器大小
if (oldCapacity == MAXIMUM_CAPACITY) { //是否超过最大值：1073741824
threshold = Integer.MAX_VALUE;
return;
}
//新的数组：大小为 oldCapacity * 2
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
/*
* 重新计算阀值 = newCapacity * loadFactor > MAXIMUM_CAPACITY + 1 ?
* newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
*/
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//将元素插入到新数组中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}3.2、负载因子
为了确认何时需要调整Map容器，Map使用了一个额外的参数并且粗略计算存储容器的密度。在Map调整大小之前，使用”负载因子”来指示Map将会承担的“负载量”，也就是它的负载程度，当容器中元素的数量达到了这个“负载量”，则Map将会进行扩容操作。负载因子、容量、Map大小之间的关系如下：负载因子 * 容量 > map大小 ----->调整Map大小。
例如：如果负载因子大小为0.75（HashMap的默认值），默认容量为11，则 11 * 0.75 = 8.25 = 8，所以当我们容器中插入第八个元素的时候，Map就会调整大小。
负载因子本身就是在控件和时间之间的折衷。当我使用较小的负载因子时，虽然降低了冲突的可能性，使得单个链表的长度减小了，加快了访问和更新的速度，但是它占用了更多的控件，使得数组中的大部分控件没有得到利用，元素分布比较稀疏，同时由于Map频繁的调整大小，可能会降低性能。但是如果负载因子过大，会使得元素分布比较紧凑，导致产生冲突的可能性加大，从而访问、更新速度较慢。所以我们一般推荐不更改负载因子的值，采用默认值0.75.
最后
推荐阅读：
java提高篇（二三）—–HashMap
java提高篇（二五）—–HashTable
Java提高篇（二六）-----hashCode
Java提高篇（二七）—–TreeMap
以上就是Java提高篇（三三）-----Map总结的内容，更多相关内容请关注PHP中文网（www.php.cn）！