Java中的HashMap和HashTable

对于 Map ,最直观就是理解就是键值对,映射,key-value 形式。一个映射不能包含重复的键,一个键只能有一个值。平常我们使用的时候,最常用的无非就是 HashMap。

HashMap 实现了 Map 接口,允许使用 null 值 和 null 键,并且不保证映射顺序。

HashMap 有两个参数影响性能:

初始容量:表示哈希表在其容量自动增加之前可以达到多满的一种尺度
加载因子:当哈希表中的条目超过了容量和加载因子的乘积的时候,就会进行重哈希操作。
如下成员变量源码:

1 static final float DEFAULT_LOAD_FACTOR = 0.75f;
2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
3 transient Node<K,V>[] table;

可以看到,默认加载因子为 0.75, 默认容量为 1 << 4,也就是 16。加载因子过高,容易产生哈希冲突,加载因子过小,容易浪费空间,0.75是一种折中。

另外,整个 HashMap 的实现原理可以简单的理解成:当我们 put 的时候,首先根据 key 算出一个数值 x,然后在 table[x] 中存放我们的值。这样有一个好处是,以后的 get 等操作的时间复杂度直接就是O(1),因为 HashMap 内部就是基于数组的一个实现。

hash(key) 这个就是表示要根据 key 值算出一个数值,以此来决定在 table 数组的哪一个位置存放我们的数值。(Ps:这个 hash(key) 方法 也是大有讲究的,会严重影响性能,实现得不好会让 HashMap 的 O(1) 时间复杂度降到 O(n),在JDK8以下的版本中带来灾难性影响。它需要保证得出的数在哈希表中的均匀分布,目的就是要减少哈希冲突)

重要说明一下:

JDK8 中哈希冲突过多,链表会转红黑树,时间复杂度是O(logn),不会是O(n) 
JDK8 中哈希冲突过多,链表会转红黑树,时间复杂度是O(logn),不会是O(n) 
JDK8 中哈希冲突过多,链表会转红黑树,时间复杂度是O(logn),不会是O(n) 
然后,我们再看到:

1 if ((p = tab[i = (n - 1) & hash]) == null)
2     tab[i] = newNode(hash, key, value, null);
3 else {
4     ......

这就表示,如果没有 哈希冲突,那么就可以放入数据 tab[i] = newNode(hash, key, value, null); 如果有哈希冲突,那么就执行 else 需要解决哈希冲突。

那么放入数据 其实就是 建立一个 Node 节点,该 Node节点有属性 key,value,分别保存我们的 key 值 和 value 值,然后再把这个 Node 节点放入到 table 数组中,并没有什么神秘的地方。

 1 static class Node<K,V> implements Map.Entry<K,V> {
 2     final int hash;
 3     final K key;
 4     V value;
 5     Node<K,V> next;
 6
 7     Node(int hash, K key, V value, Node<K,V> next) {
 8         this.hash = hash;
 9         this.key = key;
10         this.value = value;
11         this.next = next;
12     }
13 }

上述可以看到 Node 节点中 有一个 Node<k,v> next; ,其实仔细思考下就应该知道这个是用来解决哈希冲突的。下面再看看是如何解决哈希冲突的:

哈希冲突:通俗的讲就是首先我们进行一次 put 操作,算出了我们要在 table 数组的 x 位置放入这个值。那么下次再进行一个 put 操作的时候,又算出了我们要在 table 数组的 x 位置放入这个值,那之前已经放入过值了,那现在怎么处理呢?

其实就是通过链表法进行解决。

首先,如果有哈希冲突,那么:

1 if (p.hash == hash &&
2     ((k = p.key) == key || (key != null && key.equals(k))))
3 e = p;

需要判断 两者的 key 是否一样的,因为 HashMap 不能加入重复的键。如果一样,那么就覆盖,如果不一样,那么就先判断是不是 TreeNode 类型的:

 else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

这里表示 是不是现在已经转红黑树了(在大量哈希冲突的情况下,链表会转红黑树),一般我们小数据的情况下,是不会转的,所以这里暂时不考虑这种情况(Ps:本人也没太深入研究红黑树,所以就不说这个了)。

如果是正常情况下,会执行下面的语句来解决哈希冲突:

 1 for (int binCount = 0; ; ++binCount) {
 2     if ((e = p.next) == null) {
 3         p.next = newNode(hash, key, value, null);
 4         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 5             treeifyBin(tab, hash);
 6         break;
 7     }
 8     if (e.hash == hash &&
 9             ((k = e.key) == key || (key != null && key.equals(k))))
10         break;
11     p = e;
12 }

这里其实就是用链表法来解决。并且:

冲突的节点放在链表的最下面。
冲突的节点放在链表的最下面。
冲突的节点放在链表的最下面。

因为 首先有:p = tab[i = (n - 1) & hash] ,再 for 循环,然后有 if ((e = p.next) == null) { ,并且如果 当前节点的下一个节点有值的话,那么就 p = e;,这就说明了放在最下面。

时间: 03-06

Java中的HashMap和HashTable的相关文章

Java中的HashMap和HashTable到底哪不同?

学习Java的同学注意了!!! 学习过程中遇到什么问题或者想获取学习资源的话,欢迎加入Java学习交流群,群号码:456544752  我们一起学Java! HashMap和HashTable有什么不同?在面试和被面试的过程中,我问过也被问过这个问题,也见过了不少回答,今天决定写一写自己心目中的理想答案. 代码版本 JDK每一版本都在改进.本文讨论的HashMap和HashTable基于JDK 1.7.0_67.源码见这里 1. 时间 HashTable产生于JDK 1.1,而HashMap产生

java中的HashMap解析

这篇文章准备从源码的角度带大家分析一下java中的hashMap的原理,在了解源码之前,我们先根据自己的理解创建一个hashMap. 先说明一下创建的具体原理是这样的,所谓hashMap,必然是用hash方法来区分不同的key值.学过hash的都知道,我们解决hash冲突的一种方法就是使用散列和桶,首先确定所在的桶号,然后在桶里面逐个查找.其实我们也可以单纯使用数组实现map,使用散列是为了获得更高的查询效率. 要写自己的hashmap前,必须说明一下两个方法,就是hashcode()和equa

java读书笔记---HashMap和HashTable

首先来说说HashMap,HashMap是一个类,Java中所有的类都继承自一个Object类.Object类中定义了hashCode()方法,换言之,任何类都会有这个hashCode()方法. 因此key.hashCode()函数调用的是key键值类型自带的哈希函数,返回int型散列值. 先来看HashMap中定义的两个方法 方法一: static final int hash(Object key) { //jdk1.8 & jdk1.7 int h; // h = key.hashCode

深入理解Java中的HashMap

HashMap继承自抽象类AbstractMap,抽象类AbstractMap实现了Map接口.关系图如下所示: import java.util.*; public class SimpleMap<K,V> extends AbstractMap<K,V> { //keys存储所有的键 private List<K> keys = new ArrayList<K>(); //values存储所有的值 private List<V> values

浅析java中的hashMap

?  HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,HashSet 是 Set 接口的常用实现类.虽然 HashMap 和 HashSet 实现的接口规范不同,但它们底层的 Hash 存储机制完全一样,甚至 HashSet 本身就采用 HashMap 来实现的. 通过 HashMap.HashSet 的源代码分析其 Hash 存储机制集合和引用 就像引用类型的数组一样,当我们把 Ja

Java集合(17)--HashMap、Hashtable和ConcurrentHashMap的比较

1. 数据结构 都是数组+拉链实现的哈希表,但是具体实现上差别大了 2. 并发 Hashtable全表锁 HashMap多线程不安全,需要自己封装 ConcurrentHashMap加细粒度锁,读不加锁,如果读到空值再加锁.注意这三个关键字final,transient,volatile 3. null Hashtable不允许用 null作为键和值 HashMap允许全局最多一个null键,但是允许无数个null值 ConcurrentHashMap不允许用 null作为键和值

java中对HashMap遍历的方式

第一种是利用HashMap的entrySet()方法: Map<String,String> map = new HashMap<String,String>(); Iterator iter = map.entrySet().iterator(); while (iter.hasNext()) { Map.Entry entry = (Map.Entry) iter.next(); String key = entry.getKey(); String val = entry.g

Java中关于HashMap的使用和遍历

1:使用HashMap的一个简单例子 package com.pb.collection; import java.util.HashMap; import java.util.Iterator; import java.util.Set; import java.util.Map.Entry; public class HashMapDemo { public static void main(String[] args) { HashMap<String, String> hashMap

Java 中的 ==, equals 与 hashCode 的区别与联系

一.概述 1.概念 == : 该操作符生成的是一个boolean结果,它计算的是操作数的值之间的关系 equals : Object 的 实例方法,比较两个对象的content是否相同 hashCode : Object 的 native方法 , 获取对象的哈希值,用于确定该对象在哈希表中的索引位置,它实际上是一个int型整数 二.关系操作符 == 1.操作数的值 基本数据类型变量 在Java中有八种基本数据类型: 浮点型:float(4 byte), double(8 byte) 整型:byt