【JAVA】六 JAVA Map 一 HashMap

【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;
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【JAVA】六 JAVA Map 一 HashMap

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡