简介
Map和Set是比较常用的两种数据结构。我们在平常的编程中经常会用到他们。只是他们的内部实现机制到底是怎么样的呢?了解他们的具体实现对于我们如何有效的去使用他们也是很有帮助的。在这一篇文章里,已经对HashMap, HashSet的实现做了一个详细的讨论。这里主要是针对Map, Set这两种类型的数据结构规约和典型的HashMap,HashSet实现做一个讨论。
Map
Map是一种典型的名值对类型,它提供一种Key-Value对应保存的数据结构。我们通过Key值来访问对应的Value。和Java集合类里头其他的类不太一样,这个接口并没有继承Collection这接口。而其他的类或者接口不管是List, Set, Stack等都继承了Collection。从这一点来说,它有点像一个异类。
从前面的这部分讨论,我们可以简单的归类一下Map接口里面定义的常用操作。最常见的两种操作方法是get, put方法。get方法用于根据Key来取得所需要的Value值,而put方法用于根据特定的Key来放置对应的Value。除了这两个方法以外还有判断Key,Value是否存在的containsKey, containsValue方法。
Map类型的数据结构有一个比较好的地方就是在存取元素的时候都能够有比较高的效率。 因为每次存取元素的时候都是通过计算Key的hash值再通过一定的映射规则来实现,在理想的情况下可以达到一个常量值。
下面这部分是Map里面主要方法的列表:
方法名 | 方法详细定义 | 说明 |
containsKey | boolean containsKey(Object key); | 判断名是否存在 |
containsValue | boolean containsValue(Object value); | 判断值是否存在 |
get | V get(Object key); | 读取元素 |
put | V put(K key, V value); | 设置元素 |
keySet | Set<K> keySet(); | 所有key值合集 |
values | Collection<V> values(); | 所有value的集合 |
entrySet | Set<Map.Entry<K, V>> entrySet(); | 键值对集合 |
掌握了以上这些主要的方法介绍,对于其他部分也就很好理解。
HashMap
我们从书本上看到的hash表根据不同的需要可以有不同的实现方式,比如有的直接用线性表,有的用链表数组。在hash值的映射规则上也各不相同。在jdk的实现里,HashMap是采用链表数组形式的结构:
有了这部分的阐述,我们后面来理解它具体实现步骤就容易了很多。
内部结构
我们根据这种链表数组的类型,可以推断它内部肯定是有一个链表的结构。在HashMap内部,有一个transient Entry[] table;这样的结构数组,它保存所有Entry的一个列表。而Entry的定义是一个典型的链表结构,不过由于既要有Key也要有Value,所以包含了Key, Value两个值。他们的定义如下:
- 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;
- }
- //...
- }
这里省略了其他部分,主要把他们这个链表结构部分突出来。这部分就相当于链表里一个个的Node节点。ok,这样我们至少已经清楚了它里面是怎么组成的了。
数组增长调整
现在再来看一个地方,我们实际中设计HashMap的时候,这里面数组的长度该多少合适呢?是否需要进行动态调整呢?如果是固定死的话,如果我们需要放置的元素少了,岂不是浪费空间?如果我们要放的元素太多了,这样也会导致更大程度的hash碰撞,会带来性能方面的损失。在HashMap里面保存元素的table是可以动态增长的,它有一个默认的长度16,
- static final int DEFAULT_INITIAL_CAPACITY = 16;
- static final int MAXIMUM_CAPACITY = 1 << 30;
在HashMap的构造函数中,可以指定初始数组的长度。通过这个初始长度值,构造一个长度为2的若干次方的数组:
- // Find a power of 2 >= initialCapacity
- int capacity = 1;
- while (capacity < initialCapacity)
- capacity <<= 1;
在我们需要调整数组长度的时候,它的过程和前面讨论过的List, Queue有些类似,但是又有不同的地方。相同的地方在于,它每次也是将原来的数组长度翻倍,同时将元素拷贝过去。但是由于HashMap本身的独特性质,它需要重新做一次映射。实现这个过程的方法如下:
- 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);
- }
- /**
- * Transfers all entries from current table to newTable.
- */
- void transfer(Entry[] newTable) {
- Entry[] src = table;
- int newCapacity = newTable.length;
- for (int j = 0; j < src.length; j++) { //遍历原来的数组table
- Entry<K,V> e = src[j];
- if (e != null) {
- src[j] = null;
- do { //对该链表元素里面所有链接的<key, value>对做重新的映射
- Entry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = newTable[i];
- newTable[i] = e;
- e = next;
- } while (e != null);
- }
- }
- }
前面这部分的代码看起来比较长,实际上就是将旧的数组的元素挪到新的数组中来。因为新数组的长度不一样了,再映射的时候要对链表里面所有的元素根据新的长度进行重新映射来对应到不同的位置。
那么,我们可以看出来,元素存放的位置是和数组长度相关的。而这其中具体映射的过程和怎么放置元素的呢?我们在这里就可以找到一个入口点了。就是indexFor方法。
详细映射过程
我们要把一个<K, V>Entry放到table中间的某个位置,首先是通过计算key的hashCode值,我们都知道。在java里每个对象都有一个hashCode的方法,返回它对应的hash值。HashMap这边通过这个hash值再进行一次hash()方法的计算,得到一个int的结果。再通过indexFor将它映射到数组的某个索引。
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
- 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方法就是对传进来的key的hashCode()值再进行一次运算。indexFor方法则是具体映射的方法。因为最后得到的这个值将走为存储Entry的索引。这里采用h & (length - 1)的手法比较有意思。因为我们定义的数组长度为2的若干次方,这意味着如果我们取长度减一的值时,它的二进制数字是最高位以下的所有位为1.经过与运算之后它的结果肯定在0~2**x之间。就算前面hash方法计算出来的结果比数组长度大也没关系,因为这么一与运算,前面长出来的部分都变成0了。它这一步运算的效果相当于h % length;
有了这部分对数组长度调整和映射关系的理解,我们再来看具体的get, put方法就很容易了。
get
get方法的定义如下:
- 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)];
- // table[indexFor(hash, table.length)] 就是将indexFor运算得到的值直接映射到数组的索引
- e != null;
- e = e.next) {
- Object k;
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- //找到hash值相同的情况下可能出现hash碰撞,所以需要调用equals方法来比较是否相等
- return e.value;
- }
- return null;
- }
它这里就是一个映射,查找的过程。找到映射的点之后再和链表里的元素逐个比较,保证找到目标值。因为是hash表,会存在多个值映射到同一个index里面,所以这里还要和链表里的元素做对比。
put
put元素就是一个放置元素的过程,首先也是找到对应的索引,然后再把元素放到链表里面去。如果链表里有和元素相同的,则更新对应的value,否则就放到链表头。
- 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;
- }
- }
- //在前面的循环里面没有找到,则新建一个Entry对象,加入到链表头。
- modCount++;
- addEntry(hash, key, value, i);
- return null;
- }
addEntry方法会判断表长度,如果达到一定的阀值则调整数组的长度,将其翻倍:
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<>(hash, key, value, e);
- if (size++ >= threshold)
- resize(2 * table.length);
- }
Set
Set接口里面主要定义了常用的集合操作方法,包括添加元素,判断元素是否在里面和对元素过滤。常用的几个方法如下:
方法名 | 方法详细定义 | 说明 |
contains | boolean contains(Object o); | 判断元素是否存在 |
add | boolean add(E e); | 添加元素 |
remove | boolean remove(Object o); | 删除元素 |
retainAll | boolean retainAll(Collection<?> c); | 过滤元素 |
我们知道,集合里面要求保存的元素是不能重复的,所以它里面所有的元素都是唯一的。它的定义就有点不太一样。
HashSet
HashSet是基于HashMap实现的,在它内部有如下的定义:
- private transient HashMap<E,Object> map;
- // Dummy value to associate with an Object in the backing Map
- private static final Object PRESENT = new Object();
在它里面放置的元素都应到map里面的key部分,而在map中与key对应的value用一个Object()对象保存。因为内部是大量借用HashMap的实现,它本身不过是调用HashMap的一个代理,这些基本方法的实现就显得很简单:
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
- public boolean remove(Object o) {
- return map.remove(o)==PRESENT;
- }
- public boolean contains(Object o) {
- return map.containsKey(o);
- }
总结
在前面的参考资料里已经对HashMap做了一个很深入透彻的解析。这里在前人的基础上加入一点自己个人的理解体会。希望对以后使用类似的结构有一个更好的利用,也能够充分利用里面的设计思想。
相关推荐
掌握List集合、Set集合、Map集合的使用以及Iterator迭代器和foreach循环的使用 了解常用的集合类 熟悉泛型的使用
在Java编程语言中,集合框架提供了多种数据结构来存储和操作数据,其中`TreeMap`、`TreeSet`、`HashSet`以及`HashMap`是最常用的数据结构之一。这些集合类各自有着独特的特性和应用场景,下面将对它们进行详细介绍。...
Java 集合类详解 Java 集合类是 Java 语言中的一种基本数据结构,用于存储和操作大量数据。集合类可以分为三大类:Collection、List 和 Set。 Collection 是集合框架中的根接口,提供了基本的集合操作,如 add、...
Set接口在Java集合框架中扮演着重要角色,它是一个不包含重复元素的集合。Set接口继承自Collection接口,提供...了解和掌握这两种集合类的源码分析有助于深入理解Java集合框架的底层实现,从而更好地应用在实际开发中。
Java HashMap 类详解 本资源详细介绍了 Java 中的 HashMap 类...本资源详细介绍了 Java 中的 HashMap 类,包括其实现机制、Hash 存储机制、集合存储机制等方面的知识点,为大家提供了一个详细的 Java HashMap 类详解。
Java集合框架是Java编程中非常重要的部分,它提供了一种高效、灵活的数据组织方式。本文主要探讨了几个关键...通过对源码的深入分析,我们可以更好地掌握Java集合框架的工作原理,并根据实际需求选择最适合的数据结构。
之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。 HashMap实现了Map...
### Java集合排序及Java集合类详解 #### 一、集合框架概述 集合框架是Java编程语言的核心组件之一,用于组织和操作数据集。Java集合框架提供了多种数据结构,包括列表(List)、集(Set)和映射(Map),这些数据结构...
在本篇中,我们将深入探讨Java集合的排序机制以及集合类的详细使用。 首先,我们来了解一下Java集合的基本分类。Java集合主要分为两大类:List(列表)和Set(集)。List是一个有序的集合,允许元素重复,并且可以...
在Java编程语言中,ArrayList和HashSet是两种常用的集合类,它们各自有其特性和应用场景。在实际开发中,理解它们的差异以及如何有效地利用它们是非常重要的。本篇将深入探讨ArrayList与HashSet的区别,并分析...
"Java集合类总结" Java集合类是Java语言中的一种重要数据结构,用于存储和管理数据。Java集合类可以分为两种:Collection接口和Map接口。Collection接口有两个子接口:List接口和Set接口。List接口是有序的,可以...
### Java集合类详解总结 在Java编程中,集合框架(Collection Framework)是处理一组对象的强大工具,它提供了标准的数据结构来存储和操作这些对象。Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`...
Java集合类是Java编程语言中用于存储和管理对象的关键组件,它们构成了Java Collections Framework的核心。这个框架提供了一组高效、灵活的数据结构,使得开发者能够轻松地处理数据集合,而无需关心底层实现的复杂性...
在这个矩阵图中,你可以看到ArrayList、LinkedList、HashSet、HashMap等常见集合类的特性、性能以及它们在不同场景下的适用性。 Java集合框架是Java标准库(java.util包)的一部分,用于存储和管理对象。它的核心是...
本文将深入讲解Java集合类,特别是Collection接口和其下的List、Set,以及Map接口中的几个重要实现类。 首先,我们来看Collection接口。Collection是最基本的集合接口,它代表一组Object,即它的元素。Collection...
这篇博客文章可能详细解释了如何创建、操作和理解Java集合类的基本概念。 首先,Java集合框架主要包括接口和实现这些接口的类。接口如`List`, `Set`, `Queue`, `Map`等,定义了集合的行为和操作。而`ArrayList`, `...
首先,Java集合框架包括接口(如List、Set、Map)和实现这些接口的类(如ArrayList、HashSet、HashMap)。这些类提供了基础的数据结构和方法,如添加元素、删除元素、查找元素等。然而,标准库中的集合可能并不完全...
Java 集合类面试题总结 Java 集合类是 Java 语言中的一种重要组件,用于存储和操作数据。下面总结了 Java 集合类的一些常见问题和答案。 HashMap 和 Hashtable 的区别 HashMap 和 Hashtable 都是 Java 中的散列表...
本文将对Java集合框架中的Collection接口及其相关接口、类进行深入的探讨。 首先,Collection接口是所有单值容器的基础,它是Set、List和Queue接口的父接口。Collection接口定义了通用的操作方法,如`add()`用于...
Map集合的主要实现类有HashMap、Hashtable、TreeMap等。HashMap是哈希表实现的,key不能重复,但是value可以重复。Hashtable是线程安全的,key和value不能为null。TreeMap是对key排好序的Map,key必须实现Comparable...