Java的HashMap源码实现分析教程

1.简介

通过上面的一篇随笔我们知道了HashSet的底层是采用Map实现的，那么Map是什么?它的底层又是如何实现的呢?这下我们来分析下源码，看看具体的结构与实现。Map 集合类用于存储元素对(称作“键”和“值”)，其中每个键映射到一个值。Map.Entry是其的内部类，描述Map中的按键/数值对。需要指出的是 Map,允许null的键也允许null的值。它的实现主要有HashMap和sortedMap,其中SortedMap扩展了Map使按键保持升序排列，下面我们简要分析下HashMap的具体实现。首先给出一个应用举例：

 

 代码如下 复制代码

package com.test.collections;

 

import java.util.Collection;

import java.util.HashMap;

import java.util.Map;

import java.util.Set;

 

public class HashMapTest {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Map<String,String> map = new HashMap<String,String>();

        map.put("A", "A");

        map.put("D", "D");

        map.put("S", "S");

        map.put("C", "C");

        map.put("B", "B");

        map.put("W", "W");

         

        System.out.println(map.size());

        System.out.println(map.isEmpty());

        System.out.println(map.containsKey("A"));//boolean

        System.out.println(map.containsValue("A"));;//boolean

        System.out.println(map.get("A"));

        System.out.println(map.remove("A"));

        map.putAll(map);

        Set<String> keySet = map.keySet();

        Collection<String>  values = map.values();

        Set<Map.Entry<String, String>> entry = map.entrySet();

        map.clear();

    }

 

}

 

2.继承结构

HashMap直接继承了AbstractMap类，实现了Map

DEFAULT_INITIAL_CAPACITY：默认的初始化容量(16);

MAXIMUM_CAPACITY：能够允许的最大容量(1 << 30);

DEFAULT_LOAD_FACTOR：缺省的加载因子(0.75);

Entry[] table：存储具体的值。

transient int size：记录Map的大小。

final float loadFactor：加载因子。

上面的属性中除了一个Entry类型，这个是什么意思呢。原来这里面就是维护Map键值的类，用来存储Map的具体值的，让我们来看下它的具体实现结构：

 

 代码如下 复制代码

static class Entry<K,V> implements Map.Entry<K,V> {
   final K key;
   V value;
   Entry<K,V> next;
   final int hash;

   /**
    * Creates new entry.
    */
   Entry(int h, K k, V v, Entry<K,V> n) {
       value = v;
       next = n;
       key = k;
       hash = h;
   }

   public final K getKey() {
       return key;
   }

   public final V getValue() {
       return value;
   }

   public final V setValue(V newValue) {
   V oldValue = value;
       value = newValue;
       return oldValue;
   }

   public final 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 final int hashCode() {
       return (key==null   ? 0 : key.hashCode()) ^
              (value==null ? 0 : value.hashCode());
   }

   public final String toString() {
       return getKey() + "=" + getValue();
   }

   /**
    * This method is invoked whenever the value in an entry is
    * overwritten by an invocation of put(k,v) for a key k that's already
    * in the HashMap.
    */
   void recordAccess(HashMap<K,V> m) {
   }

   /**
    * This method is invoked whenever the entry is
    * removed from the table.
    */
   void recordRemoval(HashMap<K,V> m) {
   }
}

 

Entry

3.源码解析

a:构造函数

 

 代码如下 复制代码

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);

    // Find a power of 2 >= initialCapacity
    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 * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

void init() {
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
        Map.Entry<? extends K, ? extends V> e = i.next();
        putForCreate(e.getKey(), e.getValue());
    }
}

 

构造方法只需要说明第一个的即可，其他的都是传递一些缺省的参数值然后调用第一个构造方法实现具体的操作。重点看下第一个构造方法。它首先判断一下传入的容量是否合法以及加载因子是否合法。如果容量操作最大值是需要将它重置的，但是如果传入的值为负数是要抛出异常的。然后根据容量与加载因子的乘积得出临界值并且赋值给属性threshold，然后通过 table = new Entry[capacity]分配存储空间，完成了构造过程。Init()方法为空，不知道做了什么事情。

2.hash(int h)

 

 代码如下 复制代码
static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

 

根据Hash 值确定键的位置，如果传入的为null,那么返回的hash值就是为0，索引值就是0.

3.size(),isEmpty()

 

 代码如下 复制代码
public int size() {
     return size;
 }
 
 /**
  * Returns <tt>true</tt> if this map contains no key-value mappings.
  *
  * @return <tt>true</tt> if this map contains no key-value mappings
  */
 public boolean isEmpty() {
     return size == 0;
 }

 

Map大小就是直接返回属性值size的值，判断是否为空就是如果size为0说明为空否则不为空。

4.get(Object)

 

 代码如下 复制代码
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

 

根据键返回对应的值，首先判断键是否为null，如果为空的话就调用getForNullKey()返回空键对应的值只会有一个。其实也就是返回Map的第一个值，因为null对应的hash值为0，存储位置就是第一个。然后调用hash()方法返回唯一对应的hash值，然后再循环遍历这个 Map，如果发现Hash值相等就直接返回它的值，如果没有发现对应的值就返回null.

5.containsKey(Object )

 

 代码如下 复制代码
public boolean containsKey(Object key) {
     return getEntry(key) != null;
 }
 final Entry<K,V> getEntry(Object key) {
     int hash = (key == null) ? 0 : hash(key.hashCode());
     for (Entry<K,V> e = table[indexFor(hash, table.length)];
          e != null;
          e = e.next) {
         Object k;
         if (e.hash == hash &&
             ((k = e.key) == key || (key != null && key.equals(k))))
             return e;
     }
     return null;
 }

 

判断是否含有某个值就是首先获取这个值，如果获取的值不为空就说么这个对象是存在的。获取key的方法是根据getKey()方法来实现的。首先获取Hash值，然后遍历循环这个Entry数组，如果遇到键相同就返回否则就返回为null.

6.put(K，V)

 

 代码如下 复制代码
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.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) {
 Entry<K,V> e = table[bucketIndex];
     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
     if (size++ >= threshold)
         resize(2 * table.length);
 }
 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);
     table = newTable;
     threshold = (int)(newCapacity * loadFactor);
 }

 

我们是通过put(K,V)方法来添加对象到Map中的，首先判断传入的Key是否为null，如果为null就直接调用 putForNullKey(value)方法将null的键对应上值。如果不为空就首先获取K对应的Hash值,然后遍历循环这个Map，如果值已经存在就更新覆盖value并且返回返回老的value，否则的话就调用addEntry(hash, key, value, i);插入新值。插入及很简单了，New一个Entry对象然后确定数组位置指定值即可。

4.其他

HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量是哈希表中数据的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作(即重建内部数据结构)，从而哈希表将具有大约两倍的数目。

时间： 2024-10-27 21:51:00

Java的HashMap源码实现分析教程的相关文章

Java集合---HashMap源码剖析

Java集合---HashMap源码剖析   一.HashMap概述二.HashMap的数据结构三.HashMap源码分析     1.关键属性     2.构造方法     3.存储数据     4.调整大小      5.数据读取                       6.HashMap的性能参数                       7.Fail-Fast机制   一.HashMap概述 HashMap基于哈希表的 Map 接口的实现.此实现提供所有可选的映射操作,并允许使用 

java.util.HashMap源码要点浅析

1.散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法.链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位:开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位.java.util.HashMap采用的链表法的方式,链表是单向链表,因此在删除过程中要自己维持prev节点,我想不采用双向链表是从节省空间考虑.一个典型的查找过程: for (Entry<K,V> e = table[indexFor(hash, ta

Android 消息处理机制源码详细分析教程

Android中被使用的消息队列的代码在目录\sources\android-22\android\os下,主要涉及到以下几个类文件 Handler.java  在这里面代表一个消息实体对象Looper.java  主要用来监听MessageQueue的消息,他存放于ThreadLocal中Message.java  主要用来处理消息的发送,以及响应消息的业务处理MessageQueue.java  是一个单独的线程,可与Looper整合,实现一个完全独立的消息处理机制 Message.java

[Java] HashMap源码分析

版权声明:请尊重个人劳动成果,转载注明出处,谢谢!http://blog.csdn.net/amazing7/article/details/51283211 目录(?)[+] 1.概述 Hashmap继承于AbstractMap,实现了Map.Cloneable.Java.io.Serializable接口.它的key.value都可以为null,映射不是有序的.    Hashmap不是同步的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronize

HashMap源码分析（jdk1.8）

HashMap源码前前后后看了好几次,也和同事分享过好几次,每次都有新的收获. 分享也是一种提高! 本文首写于个人云笔记(点击访问),经多次修改,短期内不会有重大修改了,现发于此,有任何问题欢迎交流指正.     本文最初借鉴于http://www.cnblogs.com/hzmark/archive/2012/12/24/HashMap.html,其基于jdk1.6,自己分析jdk1.8后,发现有很大的不同,遂记录于此.     Java最基本的数据结构有数组和链表.数组的特点是空间连续(大小

Java集合源码剖析：HashMap源码剖析

HashMap简介 HashMap是基于哈希表实现的,每一个元素是一个key-value对,其内部通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长. HashMap是非线程安全的,只是用于单线程环境下,多线程环境下可以采用concurrent并发包下的concurrentHashMap. HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆. HashMap源码剖析 HashMap的源码如下(加入了比较详细的注释): pac

自定义View系列教程03--onLayout源码详尽分析

探索Android软键盘的疑难杂症 深入探讨Android异步精髓Handler 详解Android主流框架不可或缺的基石 站在源码的肩膀上全解Scroller工作机制 Android多分辨率适配框架(1)- 核心基础 Android多分辨率适配框架(2)- 原理剖析 Android多分辨率适配框架(3)- 使用指南 自定义View系列教程00–推翻自己和过往,重学自定义View 自定义View系列教程01–常用工具介绍 自定义View系列教程02–onMeasure源码详尽分析 自定义View

自定义View系列教程02--onMeasure源码详尽分析

探索Android软键盘的疑难杂症 深入探讨Android异步精髓Handler 详解Android主流框架不可或缺的基石 站在源码的肩膀上全解Scroller工作机制 站在源码的肩膀上全解Scroller工作机制 Android多分辨率适配框架(1)- 核心基础 Android多分辨率适配框架(2)- 原理剖析 Android多分辨率适配框架(3)- 使用指南 自定义View系列教程00–推翻自己和过往,重学自定义View 自定义View系列教程01–常用工具介绍 自定义View系列教程02–

HashMap源码解读（转）

 http://www.360doc.com/content/10/1214/22/573136_78188909.shtml 最近朋友推荐的一个很好的工作,又是面了2轮没通过,已经是好几次朋友内推没过了,觉得挺对不住朋友的.面试反馈有一方面是有些方面理解思考的还不够,平时也是项目进度比较紧,有些方面赶进度时没有理解清楚的后面接着做新需求没时间或者给忘了.以后还是得抽时间深入理解学习一些知识了,后面重点是知识深度,多思考. 今天把面试问的较多的HashMap源码看了下,相关知识做了个总结,希望对