1. LinkedHashMap概述：
LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
&& LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。&& LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。&& 注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。&&
默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。 &可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素。&
2. LinkedHashMap的实现：
&& 对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap的源代码：
Java代码&&
public&class&LinkedHashMap&K,&V&&extends&HashMap&K,&V&&implements&Map&K,&V&&&&&
&1) 成员变量：
&& LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：
Java代码&&
&private&final&boolean&accessO&&
private&transient&Entry&K,V&&&&
private&static&class&Entry&K,V&&extends&HashMap.Entry&K,V&&{&&
&&&&Entry&K,V&&before,&&&
HashMap.Entry:
Java代码&&
static&class&Entry&K,V&&implements&Map.Entry&K,V&&{&&
&&&&&&&&final&K&&&
&&&&&&&&V&&&
&&&&&&&&Entry&K,V&&&&
&&&&&&&&final&int&&&
&&&&&&&&Entry(int&h,&K&k,&V&v,&Entry&K,V&&n)&{&&
&&&&&&&&&&&&value&=&v;&&
&&&&&&&&&&&&next&=&n;&&
&&&&&&&&&&&&key&=&k;&&
&&&&&&&&&&&&hash&=&h;&&
&&&&&&&&}&&
&&&&2) 初始化：
&& 通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：
public&LinkedHashMap(int&initialCapacity,&float&loadFactor)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&accessOrder&=&false;&&
&&& 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);&&
&&&&int&capacity&=&1;&&
&&&&while&(capacity&&&initialCapacity)&&
&&&&&&&&capacity&&&=&1;&&
&&&&this.loadFactor&=&loadF&&
&&&&threshold&=&(int)(capacity&*&loadFactor);&&
&&&&table&=&new&Entry[capacity];&&
&&&&init();&&
&&& 我们已经知道LinkedHashMap的Entry元素继承HashMap的Entry，提供了双向链表的功能。在上述HashMap的构造器中，最后会调用init()方法，进行相关的初始化，这个方法在HashMap的实现中并无意义，只是提供给子类实现相关的初始化调用。&& LinkedHashMap重写了init()方法，在调用父类的构造方法完成构造后，进一步实现了对其元素Entry的初始化操作。
void&init()&{&&
&&&&header&=&new&Entry&K,V&(-1,&null,&null,&null);&&
&&&&header.before&=&header.after&=&&&
&&&&3) 存储：
&&&LinkedHashMap并未重写父类HashMap的put方法，而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m)&& ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的双向链接列表的实现。
HashMap.put:
Java代码&&
public&V&put(K&key,&V&value)&{&&
&&&&&&&&if&(key&==&null)&&
&&&&&&&&&&&&return&putForNullKey(value);&&
&&&&&&&&int&hash&=&hash(key.hashCode());&&
&&&&&&&&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.&&
&&&&&&&&&&&&&&&&e.value&=&&&
&&&&&&&&&&&&&&&&e.recordAccess(this);&&
&&&&&&&&&&&&&&&&return&oldV&&
&&&&&&&&&&&&}&&
&&&&&&&&}&&
&&&&&&&&modCount++;&&
&&&&&&&&addEntry(hash,&key,&value,&i);&&
&&&&&&&&return&null;&&
&重写方法：
Java代码&&
void&recordAccess(HashMap&K,V&&m)&{&&
&&&&&&&&&&&&LinkedHashMap&K,V&&lm&=&(LinkedHashMap&K,V&)m;&&
&&&&&&&&&&&&if&(lm.accessOrder)&{&&
&&&&&&&&&&&&&&&&lm.modCount++;&&
&&&&&&&&&&&&&&&&remove();&&
&&&&&&&&&&&&&&&&addBefore(lm.header);&&
&&&&&&&&&&&&}&&
&&&&&&&&}&&
void&addEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&createEntry(hash,&key,&value,&bucketIndex);&&
&&&&Entry&K,V&&eldest&=&header.&&
&&&&if&(removeEldestEntry(eldest))&{&&
&&&&&&&&removeEntryForKey(eldest.key);&&
&&&&}&else&{&&
&&&&&&&&if&(size&&=&threshold)&&
&&&&&&&&&&&&resize(2&*&table.length);&&
void&createEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&HashMap.Entry&K,V&&old&=&table[bucketIndex];&&
&&&&Entry&K,V&&e&=&new&Entry&K,V&(hash,&key,&value,&old);&&
&&&&table[bucketIndex]&=&e;&&
&&&&e.addBefore(header);&&
&&&&size++;&&
private&void&addBefore(Entry&K,V&&existingEntry)&{&&
&&&&after&&=&existingE&&
&&&&before&=&existingEntry.&&
&&&&before.after&=&this;&&
&&&&after.before&=&this;&&
&& LinkedHashMap重写了父类HashMap的get方法，实际在调用父类getEntry()方法取得查找的元素后，再判断当排序模式accessOrder为true时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
HashMap.containsValue:
Java代码&&
public&boolean&containsValue(Object&value)&{&&
&&&&if&(value&==&null)&&
&&&&&&&&&&&&return&containsNullValue();&&
&&&&Entry[]&tab&=&&&
&&&&&&&&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;&&
Java代码&&
public&boolean&containsValue(Object&value)&{&&
&&&&&&&&&&
&&&&&&&&if&(value==null)&{&&
&&&&&&&&&&&&for&(Entry&e&=&header.&e&!=&&e&=&e.after)&&
&&&&&&&&&&&&&&&&if&(e.value==null)&&
&&&&&&&&&&&&&&&&&&&&return&true;&&
&&&&&&&&}&else&{&&
&&&&&&&&&&&&for&(Entry&e&=&header.&e&!=&&e&=&e.after)&&
&&&&&&&&&&&&&&&&if&(value.equals(e.value))&&
&&&&&&&&&&&&&&&&&&&&return&true;&&
&&&&&&&&}&&
&&&&&&&&return&false;&&
Java代码&&
&void&transfer(HashMap.Entry[]&newTable)&{&&
&&&int&newCapacity&=&newTable.&&
&&&for&(Entry&K,&V&&e&=&header.&e&!=&&e&=&e.after)&{&&
&&&&&int&index&=&indexFor(e.hash,&newCapacity);&&
&&&&&e.next&=&newTable[index];&&
&&&&&newTable[index]&=&e;&&
public&V&get(Object&key)&{&&
&&&&Entry&K,V&&e&=&(Entry&K,V&)getEntry(key);&&
&&&&if&(e&==&null)&&
&&&&&&&&return&null;&&
&&&&e.recordAccess(this);&&
&&&&return&e.&&
void&recordAccess(HashMap&K,V&&m)&{&&
&&&&LinkedHashMap&K,V&&lm&=&(LinkedHashMap&K,V&)m;&&
&&&&if&(lm.accessOrder)&{&&
&&&&&&&&lm.modCount++;&&
&&&&&&&&remove();&&
&&&&&&&&addBefore(lm.header);&&
Java代码&&
&&&&&&&&private&void&remove()&{&&
&&&&&&&&&&&&before.after&=&&&
&&&&&&&&&&&&after.before&=&&&
&&&&&&&&}&&
Java代码&&
public&void&clear()&{&&
&super.clear();&&
&header.before&=&header.after&=&&&
&&&&5) 排序模式：
&& LinkedHashMap定义了排序模式accessOrder，该属性为boolean型变量，对于访问顺序，为true；对于插入顺序，则为false。
private&final&boolean&accessO&&
&一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。看LinkedHashMap的构造方法，如：
public&LinkedHashMap(int&initialCapacity,&float&loadFactor)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&accessOrder&=&false;&&
&&& 这些构造方法都会默认指定排序模式为插入顺序。如果你想构造一个LinkedHashMap，并打算按从近期访问最少到近期访问最多的顺序（即访问顺序）来保存元素，那么请使用下面的构造方法构造LinkedHashMap：
public&LinkedHashMap(int&initialCapacity,&&
&&&&&&&&&float&loadFactor,&&
&&&&&&&&&&&&&&&&&&&&&boolean&accessOrder)&{&&
&&&&super(initialCapacity,&loadFactor);&&
&&&&this.accessOrder&=&accessO&&
&&& 该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建LRU缓存。LinkedHashMap提供了removeEldestEntry(Map.Entry&K,V& eldest)方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。
当有新元素加入Map的时候会调用Entry的addEntry方法，会调用removeEldestEntry方法，这里就是实现LRU元素过期机制的地方，默认的情况下removeEldestEntry方法只返回false表示元素永远不过期。
Java代码& &
&&&void&addEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&&&&createEntry(hash,&key,&value,&bucketIndex);&&
&&&&&&&Entry&K,V&&eldest&=&header.&&
&&&&&&&if&(removeEldestEntry(eldest))&{&&
&&&&&&&&&&&removeEntryForKey(eldest.key);&&
&&&&&&&}&else&{&&
&&&&&&&&&&&if&(size&&=&threshold)&&&
&&&&&&&&&&&&&&&resize(2&*&table.length);&&
&&&&&&&}&&
&&&void&createEntry(int&hash,&K&key,&V&value,&int&bucketIndex)&{&&
&&&&&&&HashMap.Entry&K,V&&old&=&table[bucketIndex];&&
Entry&K,V&&e&=&new&Entry&K,V&(hash,&key,&value,&old);&&
&&&&&&&table[bucketIndex]&=&e;&&
&&&&&&&e.addBefore(header);&&
&&&&&&&size++;&&
&&&protected&boolean&removeEldestEntry(Map.Entry&K,V&&eldest)&{&&
&&&&&&&return&false;&&
此方法通常不以任何方式修改映射，相反允许映射在其返回值的指引下进行自我修改。如果用此映射构建LRU缓存，则非常方便，它允许映射通过删除旧条目来减少内存损耗。
&& 例如：重写此方法，维持此映射只保存100个条目的稳定状态，在每次添加新条目时删除最旧的条目。
private&static&final&int&MAX_ENTRIES&=&100;&&
protected&boolean&removeEldestEntry(Map.Entry&eldest)&{&&
&&&&return&size()&&&MAX_ENTRIES;&&
部分修改。
使用LinkedHashMap构建LRU的Cache
基于LinkedHashMap实现LRU缓存调度算法原理及应用
其实LinkedHashMap几乎和HashMap一样，不同的是它定义了一个Entry&K,V& header，这个header不是放在Table里，它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry&K,V&,并添加两个属性Entry&K,V& &before,after,和header结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。
阅读(...) 评论()6658人阅读
1 HashMap不是线程安全的
hastmap是一个接口 是map接口的子接口，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap允许null key和null value，而hashtable不允许。
2
HashTable是线程安全的一个Collection。
HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。 Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现。最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap 就必须为之提供外同步。 Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异。
public static void main(String args[]){HashTable h=new HashTable();h.put("用户1",new Integer(90));h.put("用户2",new Integer(50));h.put("用户3",new Integer(60));h.put("用户4",new Integer(70));h.put("用户5",new Integer(80));Enumeration e=h.elements();while(e.hasMoreElements()){System.out.println(e.nextElement());}
map 的方法：
clear()从 Map 中删除所有映射
remove(Object key)从 Map 中删除键和关联的值
put(Object key, Object value)将指定值与指定键相关联
get(Object key)返回与指定键关联的值
containsKey(Object key)如果 Map 包含指定键的映射，则返回 true
containsValue(Object value)如果此 Map 将一个或多个键映射到指定值，则返回 true
isEmpty()如果 Map 不包含键-值映射，则返回 true size()返回 Map 中的键-值映射的数目
这些都代表了Java中的集合，这里主要从其元素是否有序，是否可重复来进行区别记忆，以便恰当地使用，当然还存在同步方面的差异，见上一篇相关文章。
允许元素重复否
Collection
AbstractSet
是（用二叉树排序）
AbstractMap
使用key-value来映射和存储数据，Key必须惟一，value可以重复
是（用二叉树排序）
List 接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList。你可以将任何东西放到一个List容器中，并在需要时从中取出。ArrayList从其命名中可以看出它是一种类似数组的形式进行存储，因此它的随机访问速度极快，而LinkedList的内部实现是链表，它适合于在链表中间需要频繁进行插入和删除操作。在具体应用时可以根据需要自由选择。前面说的Iterator只能对容器进行向前遍历，而 ListIterator则继承了Iterator的思想，并提供了对List进行双向遍历的方法。 Set接口也是 Collection的一种扩展，而与List不同的时，在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。它的常用具体实现有HashSet和TreeSet类。HashSet能快速定位一个元素，但是你放到HashSet中的对象需要实现hashCode()方法，它使用了前面说过的哈希码的算法。而TreeSet则将放入其中的元素按序存放，这就要求你放入其中的对象是可排序的，这就用到了集合框架提供的另外两个实用类Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。集合框架中还有两个很实用的公用类：Collections和 Arrays。Collections提供了对一个Collection容器进行诸如排序、复制、查找和填充等一些非常有用的方法，Arrays则是对一个数组进行类似的操作。
Map是一种把键对象和值对象进行关联的容器，而一个值对象又可以是一个Map，依次类推，这样就可形成一个多级映射。对于键对象来说，像Set一样，一个Map容器中的键对象不允许重复，这是为了保持查找结果的一致性;如果有两个键对象一样，那你想得到那个键对象所对应的值对象时就有问题了，可能你得到的并不是你想的那个值对象，结果会造成混乱，所以键的唯一性很重要，也是符合集合的性质的。当然在使用过程中，某个键所对应的值对象可能会发生变化，这时会按照最后一次修改的值对象与键对应。对于值对象则没有唯一性的要求。你可以将任意多个键都映射到一个值对象上，这不会发生任何问题（不过对你的使用却可能会造成不便，你不知道你得到的到底是那一个键所对应的值对象）。Map有两种比较常用的实现： HashMap和TreeMap。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub (Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：478423次
积分：8402
积分：8402
排名：第707名
原创：328篇
转载：44篇
评论：252条
(1)(5)(1)(1)(1)(1)(8)(5)(3)(7)(4)(1)(1)(3)(12)(1)(21)(10)(4)(7)(1)(1)(1)(2)(6)(14)(17)(14)(2)(31)(7)(15)(8)(5)(5)(1)(4)(33)(36)(23)(50)出处：http://blog.csdn.net
HashMap可以说是Java中最常用的集合类框架之一，是Java语言中非常典型的数据结构，我们总会在不经意间用到它，很大程度上方便了我们日常开发。在很多Java的笔试题中也会被问到，最常见的，“HashMap和HashTable有什么区别？”，这也不是三言两语能说清楚的，这种笔试题就是考察你来笔试之前有没有复习功课，随便来个快餐式的复习就能给出简单的答案。
HashMap计划写两篇文章，一篇是HashMap工作原理，也就是本文，另一篇是多线程下的HashMap会引发的问题。这一年文章写的有点少，工作上很忙，自己业余时间也做点东西，就把博客的时间占用了，以前是力保一周一篇文章，有点给自己任务的意思，搞的自己很累，文章质量也不高，有时候写技术文章也是需要灵感的，为了举一个例子可能要绞尽脑汁，为了一段代码可能要验证好多次，现在想通了，有灵感再写，需要一定的积累，才能把自己了解的知识点总结归纳成文章。
言归正传，了解HashMap之前，我们需要知道Object类的两个方法hashCode和equals，我们先来看一下这两个方法的默认实现：
/** JNI，调用底层其它语言实现 */
public native int hashCode();
/** 默认同==，直接比较对象 */
public boolean equals(Object obj) {
return (this == obj);
equals方法我们太熟悉了，我们经常用于字符串比较，String类中重写了equals方法，比较的是字符串值，看一下源码实现：
public boolean equals(Object anObject) {
if (this == anObject) {
if (anObject instanceof String) {
String anotherString = (String) anO
int n = value.
if (n == anotherString.value.length) {
char v1[] =
char v2[] = anotherString.
int i = 0;
// 逐个判断字符是否相等
while (n-- != 0) {
if (v1[i] != v2[i])
重写equals要满足几个条件：
自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。
对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。
传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。
一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。
对于任何非空引用值 x，x.equals(null) 都应返回 false。
Object 类的 equals 方法实现对象上差别可能性最大的相等关系；即，对于任何非空引用值 x 和 y，当且仅当 x 和 y 引用同一个对象时，此方法才返回 true（x == y 具有值 true）。 当此方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
下面来说说hashCode方法，这个方法我们平时通常是用不到的，它是为哈希家族的集合类框架(HashMap、HashSet、HashTable)提供服务，hashCode 的常规协定是：
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
以下情况不 是必需的：如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
当我们看到实现这两个方法有这么多要求时，立刻凌乱了，幸好有IDE来帮助我们，Eclipse中可以通过快捷键alt+shift+s调出快捷菜单，选择Generate hashCode() and equals()，根据业务需求，勾选需要生成的属性，确定之后，这两个方法就生成好了，我们通常需要在JavaBean对象中重写这两个方法。
好了，这两个方法介绍完之后，我们回到HashMap，HashMap中我们最长用的就是put(K, V)和get(K)，我们都知道，HashMap的K值是唯一的，那如何保证唯一性呢？我们首先想到的是用equals比较，没错，这样可以实现，那随着内部元素的增多，put和get的效率将越来越低，这里的时间复杂度是O(n)，假如有1000个元素，put时需要比较1000次，实际上，HashMap很少会用到equals方法，因为其内通过一个哈希表管理所有元素，哈希是通过hash单词音译过来的，也可以称为散列表，哈希算法可以快速的存取元素，当我们调用put存值时，HashMap首先会调用K的hashCode方法，获取哈希码，通过哈希码快速找到某个存放位置，这个位置可以被称之为
bucketIndex，然后取到
bucketIndex位置已存储的元素，首先比较已有元素K和新元素K的hashCode，通过上面所述hashCode的协定可以知道，
如果hashCode不同，equals一定为false，如果hashCode相同，equals不一定为true。hashCode可能存在冲突的情况，有个专业名词叫
碰撞，两个不同的对象会产生同一个哈希码，equals方法就是哈希码碰撞时才会执行的方法，所以前面说HashMap很少会用到equals，通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在
，则存放新的键值对&K, V&。这里可能有些疑问，为什么bucketIndex位置会已经有对象，这是因为由于某些情况下，不同的对象可能会产生相同的hash，这时hash相同，而对象不同，就会发生该情况了。文字描述有些乱，通过下面的流程图来整理一下整个put过程。
现在我们知道，执行put方法后，最终HashMap的存储结构会有这三种情况，情形3是最少发生的，哈希码发生碰撞属于小概率事件。到目前为止，我们了解了两件事：
HashMap通过键的hashCode来快速的存取元素。
当不同的对象hashCode发生碰撞时，HashMap通过单链表来解决，单链表在Java中的实现就是对象的引用(复合)。
来鉴赏一下HashMap中put方法源码：
public V put(K key, V value) {
// 处理key为null，HashMap允许key和value为null
if (key == null)
return putForNullKey(value);
// 得到key的哈希码
int hash = hash(key);
// 通过哈希码计算出bucketIndex
int i = indexFor(hash, table.length);
// 取出bucketIndex位置上的元素，并循环单链表，判断key是否已存在
for (Entry&K,V& e = table[i]; e != e = e.next) {
// 哈希码相同并且对象相同时
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 新值替换旧值，并返回旧值
V oldValue = e.
e.recordAccess(this);
return oldV
// key不存在时，加入新元素
modCount++;
addEntry(hash, key, value, i);
到这里，我们了解了HashMap工作原理的一部分，那还有另一部分，如，加载因子及rehash，HashMap通常的使用规则，多线程并发时HashMap存在的问题等等，这些会留在下一章说明。
本文来自：
，原文地址：
作者：ghsau 发表于 0:11:04
阅读：142 评论：0
相关 [hashmap 解析] 推荐：
- CSDN博客编程语言推荐文章
HashMap可以说是Java中最常用的集合类框架之一，是Java语言中非常典型的数据结构，我们总会在不经意间用到它，很大程度上方便了我们日常开发. 在很多Java的笔试题中也会被问到，最常见的，“HashMap和HashTable有什么区别. ”，这也不是三言两语能说清楚的，这种笔试题就是考察你来笔试之前有没有复习功课，随便来个快餐式的复习就能给出简单的答案.
HashMap计划写两篇文章，一篇是HashMap工作原理，也就是本文，另一篇是多线程下的HashMap会引发的问题. 这一年文章写的有点少，工作上很忙，自己业余时间也做点东西，就把博客的时间占用了，以前是力保一周一篇文章，有点给自己任务的意思，搞的自己很累，文章质量也不高，有时候写技术文章也是需要灵感的，为了举一个例子可能要绞尽脑汁，为了一段代码可能要验证好多次，现在想通了，有灵感再写，需要一定的积累，才能把自己了解的知识点总结归纳成文章.
- 技术改变世界 创新驱动中国 - 《程序员》官网
DynamoDB是Amazon最新发布的NoSQL产品. 本文在介绍DynamoDB特性的基础上，将其与SimpleDB、Cassandra和MongoDB进行了分析和比较. 在NoSQL概念日益火爆的今天，市场上又增加了一个重量级的NoSQL产品—DynamoDB，它是Amazon AWS于日发布的. 一看到这个名称，很多人都会想起2007年Amazon发表的Dynamo论文. 人们经常将这篇论文与Google的BigTable相提并论，这在当时带来了相当大的影响，很多产品都借鉴了Dynamo的思想，比如Cassandra. 那什么是DynamoDB呢. 按照AWS CTO Werner Vogels的说法：“DynamoDB是一个性能好、可靠高且具有可扩展性的NoSQL云数据库服务，DynamoDB集15年分布式非关系性数据库开发之精粹，又通过内部使用考验，是AWS团队精心打造的产品.
- 移动开发 - ITeye博客
最近一直在做接口，主要用对xml的解析用的是sax,下面我对sax的几种写法做了一个测试：. System.out.println(&耗时：&+(end-start));. System.out.println(&当前 Java 虚拟机中的使用内存量：& + (freeMemory01-freeMemory02) + & 字节&);. //将正在解析的节点名称赋给preTag. 对上面的三个方法我测试了一下：. 93 milliseconds 2071984 字节
inFile01. 93 milliseconds 2055512 字节
- SQL - 编程语言 - ITeye博客
Mysql Explain 详解. 例如: explain select * from t3 where id=3952602;. 二.explain输出解释. | id | select_type | table | type
| possible_keys
| key_len | ref
| rows | Extra |.
我的理解是SQL执行的顺利的标识,SQL从大到小的执行. | id | select_type | table
| possible_keys
| key_len | ref
| rows | Extra |.
- CSDN博客研发管理推荐文章
HashMap的数据结构：
在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外. HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体.
从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表. 当新建一个HashMap的时候，就会初始化一个数组. 1.HashMap的存取实现：.
当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾.
Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下. 网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论. 1、hashmap的数据结构. 要知道hashmap是什么，首先要搞清楚它的数据结构，在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外. Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）. 从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组.
- ITeye博客
下面是handler解析数据的方法. private HashMap&String, String& map =// 存储单个解析的完整对象. private List&HashMap&String, String&& list =// 存储全部的解析对象. private String currentTag = // 正在解析的元素的标签. private String currentValue =// 正在解析的元素的值. private String nodeName =// 解析节点的名称.
- CSDN博客移动开发推荐文章
此文章仅作为学习交流所用.
转载或引用请务必注明原文地址：.
或联系作者： .
XML:extensible markup language,可扩展标记语言. 与HTML(超文本标记语言，即Hypertext Markup Language)一样,XML也是
标准通用标记语言 (SGML) 的子集，非常适合 Web 传输. XML与HTML的设计区别是：XML
被设计为传输和存储数据，其焦点是数据的内容. 而HTML 被设计用来显示数据，其焦点是数据的外观. HTML 旨在显示信息，而 XML 旨在传输信息.
- NoSQLFan
LevelDB是Google开发的一个key-value存储，其已经作为存储引擎被Riak和Kyoto Tycoon所支持(
这里)，在国内
Tair开源key-value存储也已经将LevelDB作为其持久化存储引擎，并部署在线上使用. 下面PDF就是
淘宝核心系统研发团队的那岩总结的LevelDB内部实现的长文. 如果你对LevelDB感兴趣，那就千万不要错过. PDF地址：
leveldb实现解析.pdf. cpy-leveldb：Python版的LevelDB. 用Kyoto Tycoon挂载LevelDB存储. LevelDB中的Skip List(跳跃表）.
- CSDN博客推荐文章
JSON是JavaScript Object Notation的缩写，可见JSON来源于JavaScript. JSON数据是一系列键值对的集合. JSON和JavaScript交互更加方便. JSON对数据的描述性没有XML好. JSON的速度要远远大于XML. JSON的解析要比XML的解析要方便. JSON已经被大多数开发人员所接受，在网络数据的传输当中应用非常广泛. 下面的代码就是一个JSON：. JSON是以key/value的形式存在的，key是Strng类型的，value的类型可以是一个数组，可以是一个字符串，可以是一个数值，也可以是一个布尔值，甚至可以是一个JSON对象. 一、JSONObject的创建.
是IT社区推荐资讯的索引，它由IT社区成员主动分享的来自各种RSS源的内容组成，每天都有关于IT社区关心的内容索引更新。
ITIndex 刊登的IT社区分享的内容版权属于原作者或网站，ITIndex与分享内容原作者无关。刊登内容谨为网络故障时之索引。