Javaエンジニア面接---Mapシリーズ
9938 ワード
一、Map
これはインタフェースであり、Mapのインタフェースであり、Kはキーワードのタイプを表し、Vはキー値を表す.
二、Mapの実現方法
1、HashMap
ハッシュ・テーブルを使用してキー値を格納します.格納された場所は追加の順序に関係なく,HasCode計算の値に関係している.
コンストラクション関数:(初期、ロード)
初期化時に配列が作成されます
最大長(配列の数+延長の長さ)を許可します.
1、追加されたソース:
以下から分かるように、格納されている位置はhashで計算されています.
2、TreeMap
一、以下の継承関係から分かるように、TreeMapは間接的にmapを実現する方法である.より多くのプロパティが用意されています.
きちんとした
三、Hashtableスレッドの同期、性能がよくないため、あまり使わない.SortedMapはMapの継承であり、秩序あるソートです.
メモ:transientは、データがハードディスクに格納されず、メモリにのみ格納されることを示します.
public interface Map
これはインタフェースであり、Mapのインタフェースであり、Kはキーワードのタイプを表し、Vはキー値を表す.
int size();//
boolean isEmpty();//
boolean containsValue(Object value);// value
V get(Object key);// key value
V put(K key, V value);//
V remove(Object key);// key map
void putAll(Map extends K, ? extends V> m);//
void clear();//
//Map--> set
Set keySet();// , key 1 2 3 3 2 1 。
二、Mapの実現方法
1、HashMap
ハッシュ・テーブルを使用してキー値を格納します.格納された場所は追加の順序に関係なく,HasCode計算の値に関係している.
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
コンストラクション関数:(初期、ロード)
public HashMap(int initialCapacity, float loadFactor)
初期化時に配列が作成されます
new Entry[capacity];
最大長(配列の数+延長の長さ)を許可します.
threshold = (int)(capacity * loadFactor);
1、追加されたソース:
以下から分かるように、格納されている位置はhashで計算されています.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);// null
//hash
int hash = hash(key.hashCode());
// hash
int i = indexFor(hash, table.length);
// , , ,
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
// hash ---
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//
modCount++;
//
addEntry(hash, key, value, i);
return null;
}
get hash ,
void addEntry(int hash, K key, V value, int bucketIndex) {
//
Entry e = table[bucketIndex];
// ,
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
2、TreeMap
一、以下の継承関係から分かるように、TreeMapは間接的にmapを実現する方法である.より多くのプロパティが用意されています.
きちんとした
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
public interface NavigableMap<K,V> extends SortedMap<K,V> public interface SortedMap<K,V> extends Map<K,V>
private final Entry buildFromSorted(int level, int lo, int hi,
int redLevel,
Iterator it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
//
if (hi < lo) return null;
int mid = (lo + hi) >>> 1;
Entry left = null;
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
it, str, defaultVal);
// extract key and/or value from iterator or stream
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry entry = (Map.Entry)it.next();
key = entry.getKey();
value = entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
Entry middle = new Entry<>(key, value, null);
// color nodes in non-full bottommost level red
if (level == redLevel)
middle.color = RED;
if (left != null) {
middle.left = left;
left.parent = middle;
}
if (mid < hi) {
Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
return middle;
}
三、Hashtableスレッドの同期、性能がよくないため、あまり使わない.SortedMapはMapの継承であり、秩序あるソートです.
メモ:transientは、データがハードディスクに格納されず、メモリにのみ格納されることを示します.