- 浏览: 161435 次
- 性别:
- 来自: 成都
文章分类
- 全部博客 (134)
- JAVA Collection,Map (6)
- JAVA IO (6)
- JAVA 线程 (12)
- JAVA 反射机制 (6)
- JSP (2)
- JAVASCRIPT (6)
- JAVA OOP (4)
- Struts (4)
- Hibernate (5)
- Spring (9)
- IBatis (8)
- HTML (1)
- CSS (1)
- ORACLE (1)
- Servlet (4)
- DATABASE (5)
- JAVA逻辑 (1)
- JVM学习 (8)
- 设计模式 (13)
- JDBC (1)
- JAVA XML (6)
- Jquery (4)
- IT生活 (2)
- JAVA Web Servece (2)
- EJB (2)
- C语言基础 (3)
- JAVA数据结构和算法 (4)
- C数据结构和算法 (0)
- JAVA Collection (5)
- Map (5)
- Inner Class (1)
- JVM (0)
- tomcat (0)
- 版本控制 (1)
最新评论
-
baukh789:
...我们公司最近也在推这个东西,SVN用了四五年了,猛的换一 ...
git 初使用 -
BuN_Ny:
时序图???????????????????
EA入门-4 -
308202251:
308202251 写道308202251 写道3082022 ...
Java 反射机制中 getMethod()和getDeclaredField()区别 -
308202251:
308202251 写道308202251 写道3082022 ...
Java 反射机制中 getMethod()和getDeclaredField()区别 -
308202251:
308202251 写道308202251 写道3082022 ...
Java 反射机制中 getMethod()和getDeclaredField()区别
HashMap是Java新Collection Framework中用来代替HashTable的一个实现,HashMap和HashTable的区别是: HashMap是未经同步的,而且允许null值。HashTable继承Dictionary,而且使用了Enumeration,所以被建议不要使用。
HashMap的声明如下:
public class HashMap extends AbstractMap implements Map, Cloneable,Serializable
有关AbstractMap:http://blog.csdn.net/treeroot/archive/2004/09/20/110343.aspx
有关Map:http://blog.csdn.net/treeroot/archive/2004/09/20/110331.aspx
有关Cloneable:http://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx
这个类比较复杂,这里只是重点分析了几个方法,特别是后面涉及到很多内部类都没有解释
不过都比较简单。
HashMap的声明如下:
public class HashMap extends AbstractMap implements Map, Cloneable,Serializable
有关AbstractMap:http://blog.csdn.net/treeroot/archive/2004/09/20/110343.aspx
有关Map:http://blog.csdn.net/treeroot/archive/2004/09/20/110331.aspx
有关Cloneable:http://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx
这个类比较复杂,这里只是重点分析了几个方法,特别是后面涉及到很多内部类都没有解释
不过都比较简单。
static final int DEFAULT_INITIAL_CAPACITY = 16; 默认初始化大小 static final int MAXIMUM_CAPACITY = 1 << 30; 最大初始化大小 static final float DEFAULT_LOAD_FACTOR = 0.75f; 默认加载因子 transient Entry[] table; 一个Entry类型的数组,数组的长度为2的指数。 transient int size; 映射的个数 int threshold; 下一次扩容时的值 final float loadFactor; 加载因子 transient volatile int modCount; 修改次数 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); int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY); 注意:这里应该是一个失误! 应该是:threshold =(int)(DEFAULT_INITIAL_CAPACITY * loadFactor); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } public HashMap(Map m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); } void init() {} static final Object NULL_KEY = new Object(); static Object maskNull(Object key){ return (key == null ? NULL_KEY : key); } static Object unmaskNull(Object key) { return (key == NULL_KEY ? null : key); } static int hash(Object x) { int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } 在HashTable中没有这个方法,也就是说HashTable中是直接用对象的hashCode值,但是HashMap做了改进 用这个算法来获得哈希值。 static boolean eq(Object x, Object y) { return x == y || x.equals(y); } static int indexFor(int h, int length) { return h & (length-1); } 根据哈希值和数组的长度来返回该hash值在数组中的位置,只是简单的与关系。 public int size() { return size; } public boolean isEmpty() { return size == 0; } public Object get(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e = table[i]; while (true) { if (e == null) return e; if (e.hash == hash && eq(k, e.key)) return e.value; e = e.next; } } 这个方法是获取数据的方法,首先获得哈希值,这里把null值掩饰了,并且hash值经过函数hash()修正。 然后计算该哈希值在数组中的索引值。如果该索引处的引用为null,表示HashMap中不存在这个映射。 否则的话遍历整个链表,这里找到了就返回,如果没有找到就遍历到链表末尾,返回null。这里的比较是这样的:e.hash==hash && eq(k,e.key) 也就是说如果hash不同就肯定认为不相等,eq就被短路了,只有在 hash相同的情况下才调用equals方法。现在我们该明白Object中说的如果两个对象equals返回true,他们的 hashCode应该相同的道理了吧。假如两个对象调用equals返回true,但是hashCode不一样,那么在HashMap 里就认为他们不相等。 public boolean containsKey(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e = table[i]; while (e != null) { if (e.hash == hash && eq(k, e.key)) return true; e = e.next; } return false; } 这个方法比上面的简单,先找到哈希位置,再遍历整个链表,如果找到就返回true。 Entry getEntry(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry e = table[i]; while (e != null && !(e.hash == hash && eq(k, e.key))) e = e.next; return e; } 这个方法根据key值返回Entry节点,也是先获得索引位置,再遍历链表,如果没有找到返回的是null。 public Object put(Object key, Object value) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { if (e.hash == hash && eq(k, e.key)) { Object oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, k, value, i); return null; } 首先获得hash索引位置,如果该位置的引用为null,那么直接插入一个映射,返回null。如果此处的引用不是null,必须遍历链表,如果找到一个相同的key,那么就更新该value,同时返回原来的value值。如果遍历完了没有找到,说明该key值不存在,还是插入一个映射。如果hash值足够离散的话,也就是说该索引没有被使用的话,那么不不用遍历链表了。相反,如果hash值不离散,极端的说如果是常数的话,所有的映射都会在这一个链表上,效率会极其低下。这里举一个最简单的例子,写两 个不同的类作为key插入到HashMap中,效率会远远不同。 class Good{ int i; public Good(int i){ this.i=i; } public boolean equals(Object o){ return (o instanceof Good) && (this.i==((Good)o).i) } public int hashCode(){ return i; } } class Bad{ int i; public Good(int i){ this.i=i; } public boolean equals(Object o){ return (o instanceof Good) && (this.i==((Good)o).i) } public int hashCode(){ return 0; } } 执行代码: Map m1=new HashMap(); Map m2=new HashMap(); for(int i=0;i<100;i++){ m1.put(new Good(i),new Integer(i)); //这里效率非常高 } for(int i=0;i<100;i++){ m2.put(new Bad(i),new Integer(i)); //这里几乎要崩溃 } 上面的是两个非常极端的例子,执行一下就知道差别有多大。 private void putForCreate(Object key, Object value) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { if (e.hash == hash && eq(k, e.key)) { e.value = value; return; } } createEntry(hash, k, value, i); } void putAllForCreate(Map m) { for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry e = (Map.Entry) i.next(); putForCreate(e.getKey(), e.getValue()); } } 上面的两个方法是被构造函数和clone方法调用的。 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (size < threshold || oldCapacity > newCapacity) return; Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } 这个方法在需要的时候重新分配空间,相当于ArrayList的ensureCapacity方法,不过这个更加复杂。 void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry e = src[j]; if (e != null) { src[j] = null; do { Entry next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 遍历原来的数组,如果该Entry不是null的话,说明有映射,然后遍历这个链表,把所有的映射插入到新的数组中,注意这里要从新计算索引位置。 public void putAll(Map t) { int n = t.size(); if (n == 0) return; if (n >= threshold) { n = (int)(n / loadFactor + 1); if (n > MAXIMUM_CAPACITY) n = MAXIMUM_CAPACITY; int capacity = table.length; while (capacity < n) capacity <<= 1; resize(capacity); } for (Iterator i = t.entrySet().iterator(); i.hasNext(); ) { Map.Entry e = (Map.Entry) i.next(); put(e.getKey(), e.getValue()); } } 这个方法先确定是否需要扩大空间,然后循环调用put方法。 public Object remove(Object key) { Entry e = removeEntryForKey(key); return (e == null ? e : e.value); } Entry removeEntryForKey(Object key) { Object k = maskNull(key); int hash = hash(k); int i = indexFor(hash, table.length); Entry prev = table[i]; Entry e = prev; while (e != null) { 如果e==null表示不存在 Entry next = e.next; if (e.hash == hash && eq(k, e.key)) { modCount++; size--; if (prev == e) table[i] = next; 链表的第一个元素就是要删除的,这里最好加一句 e.next=null. else prev.next = next; 存在担不是链表的第一个元素, 这里最好加一句 e.next=null. e.recordRemoval(this); return e; } prev = e; e = next; } return e; 这里其实就是return null; } 这个方法其实也不复杂,也是遍历链表,这里建议加一句e.next=null,可以改为 if(prev==e) table[i]=next; else prev.next=next; e.next=null; 这一句是多加的,可以提高效率。 这里简单说明我的看法: 因为e是被删除的节点,删除它其实就是指向它的指针指向它的后面一个节点。所以e可以作为GC回收的对象。 可以e还有一个next指针指向我们的数据,如果e没有被回收。而且此时e.next指向的节点也变为没用的了,但是 却有一个它的引用(e.next),所以虽然e的下一个节点没用了,但是却不能作为GC回收的对象,除非e先被回收。 虽然不一定会引起很大的问题,但是至少会影响GC的回收效率。就像数据库中的外键引用一样,删除起来很麻烦呀。 Entry removeMapping(Object o) { if (!(o instanceof Map.Entry)) return null; Map.Entry entry = (Map.Entry)o; Object k = maskNull(entry.getKey()); int hash = hash(k); int i = indexFor(hash, table.length); Entry prev = table[i]; Entry e = prev; while (e != null) { Entry next = e.next; if (e.hash == hash && e.equals(entry)) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } 这个方法和上面的一样。 public void clear() { modCount++; Entry tab[] = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; } 同样可以改进 public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry tab[] = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; } private boolean containsNullValue() { Entry tab[] = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; } public Object clone() { HashMap result = null; try { result = (HashMap)super.clone(); } catch (CloneNotSupportedException e) { // assert false; } result.table = new Entry[table.length]; result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this); return result; } static class Entry implements Map.Entry { final Object key; Object value; final int hash; Entry next; Entry(int h, Object k, Object v, Entry n) { value = v; next = n; key = k; hash = h; } public Object getKey() { return unmaskNull(key); } public Object getValue() { return value; } public Object setValue(Object newValue) { Object oldValue = value; value = newValue; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public int hashCode() { return (key==NULL_KEY ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public String toString() { return getKey() + "=" + getValue(); } void recordAccess(HashMap m) { } void recordRemoval(HashMap m) { } } 一个静态内部类 void addEntry(int hash, Object key, Object value, int bucketIndex) { table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]); if (size++ >= threshold) resize(2 * table.length); } 注意这个方法,插入连表的头。 可以写成这样更好理解: Entry oldHead=table[bucketIndex]; Entry newHead = new Entry(hash,key,value,oldHead); table[bucketIndex]=newHead; void createEntry(int hash, Object key, Object value, int bucketIndex) { table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]); size++; } private abstract class HashIterator implements Iterator { Entry next; int expectedModCount; int index; Entry current; HashIterator() { expectedModCount = modCount; Entry[] t = table; int i = t.length; Entry n = null; if (size != 0) { while (i > 0 && (n = t[--i]) == null) ; } next = n; index = i; } public boolean hasNext() { return next != null; } Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry e = next; if (e == null) throw new NoSuchElementException(); Entry n = e.next; Entry[] t = table; int i = index; while (n == null && i > 0) n = t[--i]; index = i; next = n; return current = 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; } } private class ValueIterator extends HashIterator { public Object next() { return nextEntry().value; } } private class KeyIterator extends HashIterator { public Object next() { return nextEntry().getKey(); } } private class EntryIterator extends HashIterator { public Object next() { return nextEntry(); } } Iterator newKeyIterator() { return new KeyIterator(); } Iterator newValueIterator() { return new ValueIterator(); } Iterator newEntryIterator() { return new EntryIterator(); } private transient Set entrySet = null; public Set keySet() { Set ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private class KeySet extends AbstractSet { public Iterator iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } } public Collection values() { Collection vs = values; return (vs != null ? vs : (values = new Values())); } private class Values extends AbstractCollection { public Iterator iterator() { return newValueIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsValue(o); } public void clear() { HashMap.this.clear(); } } public Set entrySet() { Set es = entrySet; return (es != null ? es : (entrySet = new EntrySet())); } private class EntrySet extends AbstractSet { public Iterator iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Entry candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } } private void writeObject(java.io.ObjectOutputStream s) throws IOException { s.defaultWriteObject(); s.writeInt(table.length); s.writeInt(size); for (Iterator i = entrySet().iterator(); i.hasNext(); ) { Map.Entry e = (Map.Entry) i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } private static final long serialVersionUID = 362498820763181265L; private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { s.defaultReadObject(); int numBuckets = s.readInt(); table = new Entry[numBuckets]; init(); size = s.readInt(); for (int i=0; for (int i=0; i<size; i++) { Object key = s.readObject(); Object value = s.readObject(); putForCreate(key, value); } } int capacity() { return table.length; } float loadFactor() { return loadFactor; }
发表评论
-
Integer类认识
2011-04-10 12:02 809Integer类有一个缓存,他会缓存介于-128-127之间的 ... -
HashSet与HashMap源码深度剖析
2011-04-09 00:16 6801. HashSet底层是使用HashMap实现的。当使用ad ... -
java.lang.Comparable 接口
2011-04-05 21:46 824java.lang.Comparable 接口定义的 comp ... -
ArrayList,LinkedListy内部
2011-03-27 17:10 6901.当向ArrayList添加一个对象时,实际上就是将该对象放 ... -
java Map 遍历方法
2011-03-05 14:06 834Java代码 Map map = ...
相关推荐
Java集合专题总结:HashMap和HashTable源码...本文总结了HashMap和HashTable的源码学习和面试总结,涵盖了它们的存储结构、构造方法、get和put方法的源码分析、Hash表的特点和缺点、HashTable和HashMap的区别等内容。
#### 二、HashMap线程安全问题分析 在多线程环境中,`HashMap`的主要线程安全问题包括但不限于: 1. **链表死循环问题**:在JDK 1.7中,当多个线程同时进行`put`操作时,可能会出现链表死循环的情况,这是一个严重...
4. **源码分析:HashMap** `HashMap`是`Map`接口的主要实现,它使用哈希表(数组+链表/红黑树)来存储键值对。哈希函数用于快速定位元素,链表处理哈希冲突。当链表长度超过一定阈值时,会转换为红黑树,以提高查找...
通过分析源码,开发者可以深入理解哈希表的工作原理,学习如何在易语言中实现高效的数据结构,这对于提升程序性能和优化内存管理至关重要。同时,这也为自定义数据结构或实现其他哈希表相关的功能提供了基础。
面试必考之HashMap源码分析与实现 探索JVM底层奥秘ClassLoader源码分析与案例讲解 面试必备技能之Dubbo企业实战 分布式框架Zookeeper之服务注册与订阅 互联网系统垂直架构之Session解决方案 分库分表之后分布式下...
HashSet是基于HashMap实现的,其元素存储在HashMap的key上,而value使用一个静态的默认对象。为了保证元素的唯一性,存储在HashSet中的对象必须正确地覆写hashCode和equals方法。TreeSet利用二叉树的原理对元素进行...
HashMap 是 Java 中最常用的集合类之一,它是基于哈希表实现的,提供了高效的数据存取功能。HashMap 的核心原理是将键(key)通过哈希函数转化为数组索引,然后将键值对(key-value pair)存储在数组的对应位置。...
10. **面试常见问题**:面试中常问的问题包括HashMap的扩容机制、哈希冲突解决策略、线程安全性、迭代器的使用等,还可能涉及HashMap的源码分析。 通过深入学习和理解HashMap,不仅可以提高代码的编写效率,也能在...
《HashMap 源码解析——JDK11版本》 HashMap是Java中广泛使用的非同步散列表,其设计和实现是高效且灵活的。在JDK1.8之前,HashMap的底层数据结构采用的是数组+链表的方式,这种方式称为“拉链法”来解决哈希冲突。...
通过分析和学习易语言HashMap类的源码,开发者可以深入理解哈希表的工作原理,以及易语言如何实现高效的数据结构。这对于提升编程技能,尤其是理解和优化数据结构的性能,具有很大的帮助。同时,源码也可以作为参考...
5. 源码分析: 查看`HashTable`和`HashMap`的源码,可以发现两者在内部实现上也有所不同。`HashTable`直接使用了数组+链表的方式,而`HashMap`在Java 8及以后版本引入了红黑树优化,当链表长度达到一定阈值(8)时...
本篇文章将深入探讨HashMap的内部实现原理,通过源码分析,帮助开发者更好地理解和使用这个高效的数据结构。 HashMap是一个基于哈希表的Map接口实现,它提供了快速的插入、删除和查找操作。在JDK7中,HashMap的主要...
面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...
**HashMap的源码分析**: - **构造方法**:HashMap的构造函数允许用户指定初始容量和负载因子。默认初始容量是16,负载因子是0.75。当实际存储的元素数量达到容量的75%时,HashMap会自动扩容。 - **put方法**:...
因此本文将重点分析HashMap。 HashMap实现了Map接口,允许放入null元素,除该类未实现同步外,其余跟Hashtable大致相同,跟TreeMap不同,该容器不保证元素顺序,根据需要该容器可能会对元素重新哈希,元素的顺序...
Java源码角度分析HashMap用法 Java源码角度分析HashMap用法主要介绍了Java源码角度分析HashMap用法,具有一定借鉴价值,需要的朋友可以参考下。下面我们将从HashMap的优点、缺点、使用方法、源码分析等方面进行深入...
在Java编程语言中,集合框架是一个非常重要的组成部分,它提供了数据结构和算法的实现,使得在处理各种数据存储...这个高清视频可能包含了HashMap的实例演示、源码分析以及常见问题解答,有助于深入理解和应用HashMap。
4. **性能分析**: - **插入**:插入操作可能需要计算键的哈希值并更新三个数组。虽然可能比标准HashMap多一步,但如果哈希函数设计得当,冲突较少,插入速度依然可以保持较高。 - **查找**:查找可能涉及查找键的...