程序员人生 网站导航

【JAVA】六 JAVA Map 一 HashMap

栏目:php教程时间:2016-06-03 13:22:03

【JAVA】6 JAVA Map 1 HashMap

这里写图片描述

JDK API

java.util
Interface Map

Type Parameters: K - the type of keys maintained by this map V - the type of mapped values

All Known Subinterfaces:

Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, LogicalMessageContext, MessageContext, NavigableMap<K,V>, SOAPMessageContext, SortedMap<K,V>

All Known Implementing Classes:

AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, WeakHashMap




Map

先来看看 interface Map 的定义
interface Map 定义了整体的数据结构
下面我们逐一介绍具体的实现类来讲明

package java.util; public interface Map<K,V> { int size(); boolean isEmpty(); boolean containsKey(Object key); boolean containsValue(Object value); V get(Object key); V put(K key, V value); V remove(Object key); void putAll(Map<? extends K, ? extends V> m); void clear(); Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); interface Entry<K,V> { // 子接口 K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); } boolean equals(Object o); int hashCode(); }




HashMap属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { /** * 默许初始容量,必须是2的倍数 . * 为何是2的倍数后面介绍到 . */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量 1<<30. * 必须是2的倍数 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 1个空表实例,是1个Entry类型数组 . */ static final Entry<?,?>[] EMPTY_TABLE = {}; /** * 表根据需要调剂大小。长度必须是2的幂 */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; /** * map确当前长度. */ transient int size; /** * 要调剂大小的极限值(容量*默许计算阀值参数因子) resize (capacity * load factor) * * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated. int threshold; /** * 哈希表的负载系数. * * @serial */ final float loadFactor; /** * * 这个HashMap结构修改的次数 * 结构修改是那些改变的映照 * HashMap或修改其内部结构(例如重复)。 * 这个字段是用来使迭代器的集合视图 HashMap很快失败。 * (见ConcurrentModificationException)。 * */ transient int modCount; }




HashMap 构造方法

/** * 构造1个HashMap * 初始容量 * 负载系数 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; threshold = initialCapacity; init(); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 默许初始大小 16 * 默许计算阀值参数因子 0.75 */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * 接受map子集 , 将map子集转换为HashMap类型数据 . * 默许计算阀值参数因子 .75 * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }




HashMap添加值

通过源码分析,明确清楚程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value。

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key);//根据key计算hash值 int i = indexFor(hash, table.length);//计算出索引 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; 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; }

hash 方法是位运算的进程
关于位运算可以移步到我的另外一篇文章
http://blog.csdn.net/maguochao_mark/article/details/51010289

final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

indexFor(int h, int length) 方法来计算该对象应当保存在 table 数组的哪一个索引处。

/** * 当 length 总是 2 的倍数时,h & (length⑴) * 将是1个非常奇妙的设计:假定 h=5,length=16, 那末 h & length - 1 将得到 5; * 如果 h=6, length=16, 那末 h & length - 1 将得到 6 ; * 如果 h=15,length=16, 那末 h & length - 1 将得到 15 ; * 但是当 h=16 时 , length=16 时,那末 h & length - 1 将得到 0 了;当 h=17 时 , * length=16 时,那末 h & length - 1 将得到 1 了 * 这样保证计算得到的索引值总是位于 table 数组的索引以内。 */ static int indexFor(int h, int length) { return h & (length-1); }




HashMap添加值 hashCode 相同

由于hash算法是取hashCode在进行位运算,那末难免会有hashCode相同的情况产生.
那末这个时候HashMap是怎样添加值的呢?我们来通过1段代码来讲明 .

package com.cn.mark.java.util; import java.util.HashMap; class Student { public Student(String name) { this.setName(name); } private String name; public String getName() { return name; } public void setName(String name) { this.name = name; } public int hashCode() { return 9999; // 测试 使得 hashCode 相同 } public boolean equals(Object obj) { Student student = (Student) obj; if (this.getName().equals(student.getName())) return true; return false; } } @SuppressWarnings({ "rawtypes", "unchecked" }) public class HashMapTest { public static void main(String[] args) { HashMap map = new HashMap(); map.put(new Student("zhangsan"), "zhangsan"); map.put(new Student("lisi"), "lisi"); } }
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key);//根据key计算hash值 int i = indexFor(hash, table.length);//计算出索引 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; 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; } void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex];//会取出 zhangsan 的 Student 对象 table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

我们看到createEntry时将 zhangsan 的 Student 对象 做为参数传递给了 new Entry<>(hash, key, value, e);方法.

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { static class Entry<K,V> implements Map.Entry<K,V> { Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } }

在new Entry<>(hash, key, value, e); 方法中是将 zhangsan 的 Student 对象 作为了 lisi的next属性关联这.
也就是说 hash相同时会构成1个 Entry的单项链表,最早加入的Entry会在当前链表的最末端 .





HashMap 扩大容量

       当HashMap中的元素愈来愈多的时候,hash冲突的概率也就愈来愈高,由于数组的长度是固定的。所以为了提高查询的效力,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是1个经常使用的操作,而在HashMap数组扩容以后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
       那末HashMap甚么时候进行扩容呢?当HashMap中的元素个数超过 数组大小*loadFactor时,就会进行数组扩容,loadFactor的默许值为0.75,这是1个折衷的取值。也就是说,默许情况下,数组大小为16,那末当HashMap中元素个数超过16*0.75=12的时候,就把数组的大小扩大为 2*16=32,即扩大1倍,然后重新计算每一个元素在数组中的位置,而这是1个非常消耗性能的操作,所以如果我们已预知HashMap中元素的个数,那末预设元素的个数能够有效的提高HashMap的性能

void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; 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; } } }




Fail-Fast机制

       我们知道java.util.HashMap是线程不安全的,因此如果在使用迭代器的进程中有其他线程修改了map,那末将抛出ConcurrentModificationException,这就是所谓fail-fast策略。
       这1策略在源码中的实现是通过modCount域,modCount顾名思义就是修改次数,对HashMap内容的修改都将增加这个值,那末在迭代器初始化进程中会将这个值赋给迭代器的expectedModCount。
       在迭代进程中,判断modCount跟expectedModCount是不是相等,如果不相等就表示已有其他线程修改了Map注意到modCount声明为volatile,保证线程之间修改的可见性。

private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐