本文主要向大家介绍了JAVA语言集合框架：HashMap数据结构及使用技巧，通过具体的内容向大家展示，希望对大家学习JAVA语言有所帮助。

Java集合框架：HashMap数据结构及使用技巧

一、HashMap概述

　　HashMap基于哈希表的Map接口的实现。此实现提供所有可选的映射操作，并允许使用null值和null键。（除了不同步和允许使用null之外，HashMap类与Hashtable大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Collections.synchronizedMap(new HashMap());

二、HashMap的数据结构

　　HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

图中，0~15部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点Bucket桶。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

　　首先HashMap里面实现一个静态内部类Entry，其重要的属性有key,value,next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

我们看看HashMap中Entry类的代码：

/** Entry是单向链表。    

 * 它是 “HashMap链式存储法”对应的链表。    

 *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  

**/ 

static class Entry<k,v> implements Map.Entry<k,v> {    

    final K key;    

    V value;    

    // 指向下一个节点    

    Entry<k,v> next;    

    final int hash;    

    // 构造函数。    

    // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    

    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;    

    }    

    // 判断两个Entry是否相等    

    // 若两个Entry的“key”和“value”都相等，则返回true。    

    // 否则，返回false    

    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;    

    }    

    // 实现hashCode()    

    public final int hashCode() {    

        return (key==null    0 : key.hashCode()) ^    

               (value==null  0 : value.hashCode());    

    }    

    public final String toString() {    

        return getKey() + "=" + getValue();    

    }    

    // 当向HashMap中添加元素时，绘调用recordAccess()。    

    // 这里不做任何处理    

    void recordAccess(HashMap<k,v> m) {    

    }    

    // 当从HashMap中删除元素时，绘调用recordRemoval()。    

    // 这里不做任何处理    

    void recordRemoval(HashMap<k,v> m) {    

    }    

}</k,v></k,v></k,v></k,v></k,v></k,v>

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

三、HashMap源码分析

1、关键属性

　　先看看HashMap类中的一些关键属性：

transient Entry[] table;//存储元素的实体数组

transient int size;//存放元素的个数

int threshold; //临界值   当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量

final float loadFactor; //加载因子

transient int modCount;//被修改的次数

其中loadFactor加载因子是表示Hsah表中元素的填满的程度.

若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）

冲突的机会越大,则查找的成本越高.

因此,必须在"冲突的机会"与"空间利用率"之间寻找一种平衡与折衷.这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.

　　如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。

2、构造方法

下面看看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);

         // Find a power of 2 >= initialCapacity

         int capacity = 1;   //初始容量

         while (capacity < initialCapacity)   //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂

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

     }

我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方法，否则的话就是用默认的。默认初始容量为16，默认加载因子为0.75。我们可以看到上面代码中13-15行，这段代码的作用是确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂，至于为什么要把容量设置为2的n次幂，我们等下再看。

重点分析下HashMap中用的最多的两个方法put和get

3、存储数据

　　下面看看HashMap存储数据的过程是怎样的，首先看看HashMap的put方法：

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道！