Java集合框架之Set和Map详解

目录
  • Set接口
    • HashSet
    • TreeSet
  • Map接口
    • HashMap
    • TreeMap

Set接口

set接口等同于Collection接口,不过其方法的行为有更严谨的定义。set的add方法不允许增加重复的元素。要适当地定义set的equals方法:只要俩个set包含同样的元素就认为它们是相同的,而不要求这些元素有相同的顺序。hashCode方法的定义要保证包含相同元素的俩个set会得到相同的散列码。
——Java核心技术 卷一

public interface Set<E> extends Collection<E> {
    //一些方法
}

set不允许包含相同的元素,如果调用 add 方法来添加俩个相同的元素,那么在添加第二个元素时就会返回 false。这个接口有俩个比较常用的实现类:HashSet,TreeSet。HashSet是一个没有重复元素的一个无序集合,而TreeSet是一个有序集

HashSet

HashSet 使用数组和链表来实现散列表,不同 hashcode 的值存放在不同数组下标的位置,相同 hashcode 的值存放在相同数组下标的链表上的不同位置上。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    //一些方法
}

HashSet类中有四个构造方法:

public HashSet()   //构造一个空的散列集
public HashSet(Collection<? extends E> c) //构造一个散列集,并将集合中的所有元素添加到这个散列集中
public HashSet(int initialCapacity, float loadFactor) //构造一个有指定容量和装填因子的空散列集
public HashSet(int initialCapacity)  //构造一个指定容量的空散列集

现在让我们来看一下add方法的源码:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以看到这里面是调用了 map.put() 方法,map 在HashSet中的声明如下:

private transient HashMap<E,Object> map;

由此可见HashSet和HashMap有很紧密的联系。

HashSet的底层是用一个HashMap来实现的。HashSet再添加时如何扩容问题在下文HashMap中再详细介绍。

散列表

Java中,散列表用链表,数组实现。也就可以这么理解,在数组不同索引位置上放的是一个链表,要想查找表中对象的位置,要先计算它的散列码,然后与数组长度取余,所得到的结果就是保存这个元素的索引。在保存对象时,通过这个计算方式得到了索引位置,如果这个位置没有其他元素,那就将元素直接插入到该位置就好了,如果这个位置已经有其他元素了,那么需要将这个新的对象与已有的对象进行比较,查看这个对象是否已经存在。如果不存在就在链表的末尾存储这个对象。

TreeSet

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable{
    //一些方法
}

树集是一个有序集合,可以以任意顺序将元素插入集合中。

TreeSet排序是用一个红黑树完成的,每次将一个元素添加到树中时,都会将其放置到正确的排序位置上。由于树集时有序的,所以将一个元素添加到树中要比添加到散列表中慢,所以如果不需要数据是有序的,就没必要为了排序而影响性能。

它也有四个构造函数:

public TreeSet()  //构造一个空的树集,排序方式是自然排序
public TreeSet(Comparator<? super E> comparator)  //构造一个空树集,指定比较器,就是排序方式
public TreeSet(Collection<? extends E> c)   //构造一个树集,并将集合中的所有元素添加到这个树集中
public TreeSet(SortedSet<E> s)     //构造一个树集,并增加一个集合或者有序集中的所有元素,如果是有序集的话,要使用同样的顺序。

上面提到的自然排序是用元素的 compareTo() 方法来比较元素的大小关系(比如你存入v,b,a,就会输出a,b,v),然后将集合元素按照升序排列。

Map接口

集是一个集合,允许你快速的查找现有的元素。但是要查找一个元素,需要有所要查找的那个元素的准确副本。这不是一种常见的查找方式。通常,我们知道某些关键信息,希望查找与之关联的元素。映射(map)数据结构就是为此设计的。映射用来存放键 / 值对。如果提供了键,就可以查找到值。
——Java核心技术

public interface Map<K,V> {
	int size();  //返回映射中的元素数
    V get(Object key);  //返回指定键对应的值
    V remove(Object key); //从映射中删除指定键对应的元素。
}

Java为映射提供了俩个通用的实现:HashMap和TreeMap

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

}

实现了Map接口,存储的内容是键值对(key-value)映射,将键进行散列,散列或比较函数只应用于键,与键相关的值不进行散列或比较。

HashMap底层的结构是,散列表(数组和链表)和红黑树

我用反射的方式输出了这个map的容量,可以看到如果使用无参的构造方法,那么map的容量默认为16。我们也可以通过传参的方式,来指定它的容量,值的一提的是,你指定的容量,一定要为 2 的幂次方,且要小于 int 范围内最大的 2 的幂次方数(1073741824)。

//指定容量
HashMap<String,String> map = new HashMap<String, String>(8);

这个构造方法还是调用了下面的这个构造方法,只是把默认的负载因子值传进去了:

put方法,直接看源码:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

调用put方法后,会根据键值来计算一个值(位置),然后调用putVal来存放元素。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //hash表为空或者长度为0的话,创建hash表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//resize()HashMap扩容的方法
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果位置上没有元素,就加进去,成为链表的头结点
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果这个值的类型为树结构的话,就直接添加到树中,不会判断是否超过8
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //binCount链表的长度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果链表不为空,就往下一个节点添加
                    p.next = newNode(hash, key, value, null);
                    //如果这个链表的长度大于8,就会转为红黑树存储
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        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;
    //如果里面的元素超过 threshold 的话就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

通过代码中的注释,相信你已经初步了解了 put 方法,总的来说就是添加时首先是用 k 通过哈希函数计算位置,位置上如果没有元素添加在链表的头结点,如果有插入到链表的下一个节点,当链表的长度为大于等于8时,转为红黑树存储,如果该键已经有映射关系的话,用这次的值覆盖掉之前的值,最后判断要不要扩容。如果要扩容,会扩容为原来容量的2倍。这样效率会高一些,也可以减少哈希冲突。

负载因子

上文中我们提到了负载因子,那么负载因子是什么呢?

负载因子也叫装填因子,是一个0.0~1.0之间的数,确定散列表填充的百分比,当大于这个百分比时,散列表进行再散列。在map中,也就是说,当put的元素数量超过一定值的时候,就会扩容,这个值就是负载因子*容量。

HashMap中的负载因子默认是0.75:

static final float DEFAULT_LOAD_FACTOR = 0.75f;

就是说如果map中的元素超过容量的3/4就要进行扩容。

那么为什么这里要默认为0.75呢?这了也是规定了一个相对合理的值,如果为 1 的话效率太低,满了之后才扩容;如果为0.5的话,浪费空间。所以选了一个居中的值。

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

}

它没有实现Map接口是因为AbstractMap实现了Map接口,TreeMap是一个能比较元素大小的Map集合,可以对 key 值进行大小排序。其中,可以使用自然顺序,也可以使用集合中自定义的比较器来进行排序。底层是红黑树结构。

TreeMap中运用到的红黑树结构,是数据结构的一种,相关知识太多,大家感兴趣的话可以在网上查阅资料(博主对树结构的理解不是很透彻)。

到此这篇关于Java集合框架之Set和Map详解的文章就介绍到这了,更多相关Java集合内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数据结构之Map与Set专篇讲解

    目录 ①只出现一次的数字 ②宝石与石头 ③坏键盘打字 ④复制带随机指针的链表 ①只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 输入: [2,2,1]输出: 1 首相我们可能会想到用位运算直接解决,但我们也可以用hash色条解决. public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } ret

  • Java HashSet(散列集),HashMap(散列映射)的简单介绍

    简介 本篇将简单讲解Java集合框架中的HashSet与HashMap. 散列集(HashSet) 快速入门 底层原理:动态数组加单向链表或红黑树.JDK 1.8之后,当链表长度超过阈值8时,链表将转换为红黑树. 查阅HashSet的源码,可以看到HashSet的底层是HashMap,HashSet相当于只用了HashMap键Key的部分,当需要进行添加元素操作时,其值Value始终为常量PRESENT = new Object().以下为HashSet的代码片段: private transi

  • java的各种集合为什么不安全(List、Set、Map)以及代替方案

    我们已经知道多线程下会有各种不安全的问题,都知道并发的基本解决方案,这里对出现错误的情况进行一个实际模拟,以此能够联想到具体的生产环境中. 一.List 的不安全 1.1 问题 看一段代码: public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); for (int i = 0; i < 3; i++){ new Thread(()->{ list.add(U

  • 深入解读Java三大集合之map list set的用法

    Map接口和Collection接口是所有集合框架的父接口: Collection接口的子接口包括:Set接口和List接口 Map接口的实现类主要有:HashMap.TreeMap.Hashtable.ConcurrentHashMap以及Properties等 Set接口的实现类主要有:HashSet.TreeSet.LinkedHashSet等 List接口的实现类主要有:ArrayList.LinkedList.Stack以及Vector等 List,Set,Map三者的区别?List.

  • JAVA中的 map,list,set

    目录 1.Map接口和Collection接口是所有集合框架的父接口 2.Collection集合主要有List和Set两大接口 3.Map (1)Map 存元素和取元素和删除(put.get.remove) (2)循环Map 1.Map接口和Collection接口是所有集合框架的父接口 Collection接口的子接口包括:Set接口和List接口 Map接口的实现类主要有:HashMap.TreeMap.Hashtable.ConcurrentHashMap以及Properties等 Se

  • Java多线程高并发中解决ArrayList与HashSet和HashMap不安全的方案

    1.ArrayList的线程不安全解决方案 将main方法的第一行注释打开,多执行几次,会看到如下图这样的异常信息:

  • Java 集合框架掌握 Map 和 Set 的使用(内含哈希表源码解读及面试常考题)

    目录 1. 搜索 1.1 场景引入 1.2 模型 2. Map 2.1 关于 Map 的介绍 2.2 关于 Map.Entry<K, V> 的介绍 2.3 Map 的常用方法说明 2.4 关于 HashMap 的介绍 2.5 关于 TreeMap 的介绍 2.6 HashMap 和 TreeMap 的区别 2.7 Map 使用示例代码 3. Set 3.1 关于 Set 的介绍 3.1 Set 的常用方法说明 3.3 关于 TreeSet 的介绍 3.4 关于 HashSet 的介绍 3.5

  • Java中集合List、Set和Map的入门详细介绍

    目录 一.Collection接口 二.List集合 2.1介绍 2.1.1 ArrayList(数组) 2.1.2 Vector(数组实现.线程同步) 2.1.3 LinkList(链表) 2.2 List特性 2.3 List常用方法 2.4 List总结 三.Set集合 3.1介绍 3.2 分类 3.2.1 HashSet(Hash表) 3.2.2 TreeSet(二叉树) 3.2.3 LinkHashSet(HashSet+LinkedHashMap) 四.Map集合 4.1 HashM

  • java中Map、Set、List的简单使用教程(快速入门)

    Map.Set.List List的常用方法 1.创建 List<Integer> list = new ArrayList<>(); List<Integer> list = new LinkedList<>(); //同时可以作为链表用 List<List<Integer>> list = new ArrayList<>(); 2.遍历 //本质上其实是调用Iterator for(String s:list){ Sy

  • Java集合框架之Set和Map详解

    目录 Set接口 HashSet TreeSet Map接口 HashMap TreeMap Set接口 set接口等同于Collection接口,不过其方法的行为有更严谨的定义.set的add方法不允许增加重复的元素.要适当地定义set的equals方法:只要俩个set包含同样的元素就认为它们是相同的,而不要求这些元素有相同的顺序.hashCode方法的定义要保证包含相同元素的俩个set会得到相同的散列码. --Java核心技术 卷一 public interface Set<E> exte

  • Java集合基础知识 List/Set/Map详解

    一.List Set 区别 List 有序,可重复: Set 无序,不重复: 二.List Set 实现类间区别及原理 Arraylist 底层实现使用Object[],数组查询效率高 扩容机制 1.6采用(capacity * 3)/ 2 + 1,默认容量为10: 1.7采用(capacity >> 2 + capacity)实现,位移动效率高于数学运算,右移一位等于乘以2倍: 读取速度快,写入会涉及到扩容,所以相对较慢. LinkedList底层采用双向链表,只记录 first 和 las

  • Java Spring框架简介与Spring IOC详解

    目录 Spring简介和配置 1.Spring概述 1.1 spring 是什么 1.2 Spring发展历程 1.3 Spring的优势 (理解) \1. 方便解耦,简化开发 \2. AOP 编程的支持 \3. 声明式事务的支持 \4. 方便程序的测试 \5. 方便集成各种优秀框架 \6. 降低 JavaEE API 的使用难度 \7. Java 源码是经典学习范例 1.4 Spring的体系结构(了解) 2.Spring IoC快速入门 2.1 IoC的概念和作用 2.2 Spring Io

  • Java集合 LinkedList的原理及使用详解

    LinkedList和ArrayList一样是集合List的实现类,虽然较之ArrayList,其使用场景并不多,但同样有用到的时候,那么接下来,我们来认识一下它. 一. 定义一个LinkedList public static void main(String[] args) { List<String> stringList = new LinkedList<>(); List<String> tempList = new ArrayList<>();

  • Java集合之Comparable和Comparator接口详解

    目录 Comparable接口 Comparable接口简单应用 Comparator接口 Comparator接口简单应用 Comparator接口 VS Comparable接口 总结 java提供了Comparable接口与Compatator接口,它们为数组或集合中的元素提供了排序逻辑,实现此接口的对象数组或集合可以通过Arrays.sort或Collections.sort进行自动排序 Comparable接口 一个类实现了Comparable接口,则表明这个类对象之间是可以互相比较的

  • Java 集合系列(二)ArrayList详解

    ArrayList ArrayList 是通过一个数组来实现的,因此它是在连续的存储位置存放对象的引用,只不过它比 Array 更智能,能够根据集合长度进行自动扩容. 假设让我们来实现一个简单的能够自动扩容的数组,我们最容易想到的点就是: add()的时候需要判断当前数组size+1是否等于此时定义的数组大小: 若小于直接添加即可:否则,需要先扩容再进行添加. 实际上,ArrayList的内部实现原理也是这样子,我们可以来研究分析一下ArrayList的源码 add(E e) 源码分析 /**

  • Java中如何实现不可变Map详解

    前言 有时最好不允许修改  java.util.Map, 例如跨线程共享只读数据.为此,我们可以使用Unmodifiable Map或Immutable Map. 在这个快速教程中,我们将看到它们之间的区别.然后,我们将介绍可以创建不可变Map的各种方法. 下面话不多说了,来一起看看详细的介绍吧 不可修改与不可变 Unmodifiable Map其实是一个可以修改的map的包装器,不允许直接修改它. Map<String, String> mutableMap = new HashMap<

  • Java集合框架源码分析之LinkedHashMap详解

    LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

  • Java集合框架LinkedList详解及实例

    Java集合框架LinkedList详解 LinkedList定义 package java.util; public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first;

  • java集合框架详解

    1.java集合框架概述 java SE包含了由一组类和接口组成的java集合框架(java Collection Framework,简称JCF),其主要功能是用来将存储的数据以某种结构组织,并以特定的方式来访问这些数据,其目标是提供一个处理对象集合的通用框架,减少程序员处理不同对象集合时的编码量. 集合类中的一些区别,除了它们是否支持重复元素操作外,还包括元素是否有顺序,以及是否允许添加null元素.java集合框架中根据这三个区别,将对象的存储方式分为三种类型,分别是: Set(集):对象

随机推荐