hashmap（hashmap底层实现原理）

hashmap底层实现原理

hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable

从结构实现来讲，HashMap是：数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。

扩展资料

从源码可知，HashMap类中有一个非常重要的字段，就是 Node table，即哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，除了K，V，还包含hash和next。

HashMap就是使用哈希表来存储的。哈希表为解决冲突，采用链地址法来解决问题，链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

HashMap是什么东西

HashMap，中文名哈希映射，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

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

扩展资料：

因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。

HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

参考资料来源：

百度百科-Hashmap

Java中的HashMap的工作原理是什么

一，存储方式：  Java中的HashMap是以键值对(key-value)的形式存储元素的。

二，调用原理： HashMap需要一个hash函数，它使用hashCode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，HashMap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

三，其他热性： HashMap的一些重要的特性是它的容量(capacity)，负载因子(load factor)和扩容极限(threshold resizing)。

HashMap实现了Map接口，该接口的作用主要是为客户提供三种方式的数据显示：只查看keys列表；只查看values列表，或以key-value形式成对查看。Map接口并没有定义数据要如何存储，也没有指定如何判定key是一样，因此并不是所有的Map实现都会与hashCode方法扯上关系，如TreeMap便是要求对象实现Comparator接口，通过其compare方法来比对两者是否一致，而非hashCode及equals。同理，如果我们自己实现Map接口，我们也可以直接使用数组进行数据存储使用==判定key值是否一致，依然可以完全满足Map接口的定义。

HASHMAP主要有啥用

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。
注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(…));
由所有此类的“collection 视图方法”所返回的迭代器都是快速失败 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
使用示例:
HashMap a = new HashMap();
a.put(“name“, “abcdef“); // key是name，value是字符串abcdef
System.out.println(a.get(“name“));// 根据key取得其值并输出
List list = new ArrayList();
list.add(a); // 加入1题所创建的hashmap
a = new HashMap(); // 创建另一个hashmap
a.put(“name“, “123456“);//key是name，value是字符串123456
list.add(a);// 加入另一个hashmap

java中map与hashmap的区别

看看下面这个会更好

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算法都大概一样，所以性能不会有很大的差异。

HashMap为什么哪里不安全

我们都知道HashMap是线程不安全的，在多线程环境中不建议使用，但是其线程不安全主要体现在什么地方呢，本文将对该问题进行解密。

1.jdk1.7中的HashMap

在jdk1.8中对HashMap做了很多优化，这里先分析在jdk1.7中的问题，相信大家都知道在jdk1.7多线程环境下HashMap容易出现死循环，这里我们先用代码来模拟出现死循环的情况：

public class HashMapTest {    public static void main(String args) {        HashMapThread thread0 = new HashMapThread();        HashMapThread thread1 = new HashMapThread();        HashMapThread thread2 = new HashMapThread();        HashMapThread thread3 = new HashMapThread();        HashMapThread thread4 = new HashMapThread();        thread0.start();        thread1.start();        thread2.start();        thread3.start();        thread4.start();    }}class HashMapThread extends Thread {    private static AtomicInteger ai = new AtomicInteger();    private static Map map = new HashMap《》();    @Override    public void run() {        while (ai.get() 《 1000000) {            map.put(ai.get(), ai.get());            ai.incrementAndGet();        }    }}

上述代码比较简单，就是开多个线程不断进行put操作，并且HashMap与AtomicInteger都是全局共享的。

在多运行几次该代码后，出现如下死循环情形：

其中有几次还会出现数组越界的情况：

这里我们着重分析为什么会出现死循环的情况，通过jps和jstack命名查看死循环情况，结果如下：

从堆栈信息中可以看到出现死循环的位置，通过该信息可明确知道死循环发生在HashMap的扩容函数中，根源在transfer函数中，jdk1.7中HashMap的transfer函数如下：

void transfer(Entry newTable, boolean rehash) {        int newCapacity = newTable.length;        for (Entry e : table) {            while(null != e) {                Entry 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;            }        }    }

总结下该函数的主要作用：

在对table进行扩容到newTable后，需要将原来数据转移到newTable中，注意10-12行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点。

下面进行详细分析。

1.1 扩容造成死循环分析过程

前提条件，这里假设：

  • hash算法为简单的用key mod链表的大小。

  • 最开始hash表size=2，key=3,7,5，则都在table中。

  • 然后进行resize，使size变成4。

    • 未resize前的数据结构如下：

    请点击输入图片描述

    如果在单线程环境下，最后的结果如下：

    请点击输入图片描述

    这里的转移过程，不再进行详述，只要理解transfer函数在做什么，其转移过程以及如何对链表进行反转应该不难。

    然后在多线程环境下，假设有两个线程A和B都在进行put操作。线程A在执行到transfer函数中第11行代码处挂起，因为该函数在这里分析的地位非常重要，因此再次贴出来。

    请点击输入图片描述

    此时线程A中运行结果如下：

    请点击输入图片描述

    线程A挂起后，此时线程B正常执行，并完成resize操作，结果如下：

    请点击输入图片描述

    这里需要特别注意的点：由于线程B已经执行完毕，根据Java内存模型，现在newTable和table中的Entry都是主存中最新值：7.next=3，3.next=null。

    此时切换到线程A上，在线程A挂起时内存中值如下：e=3，next=7，newTable=null，代码执行过程如下：

  • newTable=e —-》 newTable=3e=next —-》 e=7

    • 此时结果如下：

    请点击输入图片描述

    继续循环：

  • e=7next=e.next —-》 next=3【从主存中取值】e.next=newTable —-》 e.next=3【从主存中取值】newTable=e —-》 newTable=7e=next —-》 e=3

    • 结果如下：

    请点击输入图片描述

    再次进行循环：

  • e=3next=e.next —-》 next=nulle.next=newTable —-》 e.next=7 即：3.next=7newTable=e —-》 newTable=3e=next —-》 e=null

    • 注意此次循环：e.next=7，而在上次循环中7.next=3，出现环形链表，并且此时e=null循环结束。

    结果如下：

    请点击输入图片描述

    在后续操作中只要涉及轮询hashmap的数据结构，就会在这里发生死循环，造成悲剧。

    1.2 扩容造成数据丢失分析过程

    遵照上述分析过程，初始时：

    请点击输入图片描述

    线程A和线程B进行put操作，同样线程A挂起：

    请点击输入图片描述

    此时线程A的运行结果如下：

    请点击输入图片描述

    此时线程B已获得CPU时间片，并完成resize操作：

    请点击输入图片描述

    同样注意由于线程B执行完成，newTable和table都为最新值：5.next=null。

    此时切换到线程A，在线程A挂起时：e=7，next=5，newTable=null。

    执行newtable[i]=e，就将7放在了table的位置，此时next=5。接着进行下一次循环：

  • e=5next=e.next —-》 next=null，从主存中取值e.next=newTable —-》 e.next=5，从主存中取值newTable=e —-》 newTable=5e=next —-》 e=null

    • 将5放置在table位置，此时e=null循环结束，3元素丢失，并形成环形链表。并在后续操作hashmap时造成死循环。

    请点击输入图片描述

    2.jdk1.8中HashMap

    在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全，这里我们看jdk1.8中HashMap的put操作源码：

  • final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node tab; Node p; int n, i;        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        if ((p = tab[i = (n – 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素            tab[i] = newNode(hash, key, value, null);        else {            Node e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount 》= TREEIFY_THRESHOLD – 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        if (++size 》 threshold)            resize();        afterNodeInsertion(evict);        return null;    }

    • 这是jdk1.8中HashMap中put操作的主函数， 注意第6行代码，如果没有hash碰撞则会直接插入元素。

    如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。

    假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。

    总结

    首先HashMap是线程不安全的，其主要体现：

  • 在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。

  • 在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

hashmap可以重复吗

这个问题很好回答，key肯定是不能重复，如果两个value的key相同，到时候就无法准确读取value值了
本质上相同不代表“表面上”不可以相同，下面请看“表面上”相同key但是不同value的例子
class A{
private String code;
private String name;
@Override
public int hashCode() {
// TODO Auto-generated method stub
return code.hashCode()+name.hashCode();
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return code.toString()+name.toString();
}

}
public static void testHashMap(){
Map map = new HashMap();
A a1 = new A();
a1.setCode(“123“);
a1.setName(“456“);
map.put(a1, “test1“);
System.out.println(map);
a1.setCode(“789“);
map.put(a1, “test2“);
System.out.println(map);
}
输出结果
{123456=test1}
{789456=test1, 789456=test2}
会发现“表面上”是相同的，出现这种结果本质原因是在于tostring方法的转化，但是它们在hashmap数据结构中hashcode是不一样，所以对应的key也是不一样的。

java中的HashMap类是做什么用的

java中HashMap类是用来存储具有键值对特征的数据。例如现在需要按照员工号来存储大量的员工信息，那么就可以使用HashMap，将员工号作为键，员工对象作为值来存储到HashMap中，其中使用HashMap时需要注意，HashMap是线程不同步的，多线程使用时，需要注意；并且HashMap允许null值作为键和值。

HashMap为什么不安全

有两个原因

  1. 存放数据时,HashMap不是线程安全的

    比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

  2. HashMap在容量不足的时候会进行resize,将自己扩容为原来的两倍,而reszie不是线程安全的

    假设有两个线程同时需要执行resize操作，我们原来的桶数量为2，记录数为3，需要resize桶到4，原来的记录分别为：[3,A],[7,B],[5,C]，在原来的map里面，我们发现这三个entry都落到了第二个桶里面。 假设线程thread1执行到了transfer方法的Entry next = e.next这一句，然后时间片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，需要注意的是，此时的[7,B]的next为[3,A]。此时线程thread1重新被调度运行，此时的thread1持有的引用是已经被thread2 resize之后的结果。线程thread1首先将[3,A]迁移到新的数组上，然后再处理[7,B]，而[7,B]被链接到了[3,A]的后面，处理完[7,B]之后，就需要处理[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]形成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。

hashtable 与hashmap有什么区别

b.也许最重要的不同是Hashtable的方法是同步的，而HashMap的方法不是。这就意味着，
虽然你可以不用采取任何特殊的行为就可以在一个 多线程的应用程序中用一个Hashtable，
但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法，
它创建一个线程安全的Map对象，并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。
这么做的结果就是当你不需要同步时，你不能切断Hashtable中的同步（比如在一个单线程的应用程序中），
而且同步增加了很多处理费用。
c.第三点不同是，只有HashMap可以让你将空值作为一个表的条目的key或value。
HashMap中只有一条记录可以是一个空的key，但任意数量的条目可以是空的value。
这就是说，如果在表中没有发现搜索键，或者如果发现了搜索键，但它是一个空的值，那么get()将返回null。
如果有必要，用containKey()方法来区别这两种情况。