专栏首页营琪的小记录算法:列表List、映射Map、集合Set-理论

算法:列表List、映射Map、集合Set-理论


下面通过一张List、map、set图,让大家回想起如何使用这些类

列表List

列表,该接口的用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引(列表中的位置)访问元素,并搜索列表中的元素。与集合不同,列表通常允许重复元素。

Java中的list是怎么实现的?

我们看看List的实现类

有很多类实现了List接口,我们比较熟悉的 ArrayList、LinkedList、Stack等等,我们从中选区ArrayList类观察一下源码,看看是怎么实现的。

Java中ArrayList的添加元素方法,简要分析

package java.util.ArrayList;
    transient Object[] elementData;             // non-private to simplify nested class access
    public ArrayList() {                        //构造函数
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    private int size;
    public boolean add(E e) {                                                    //添加方法        
        ensureCapacityInternal(size + 1);                                         //必要检查步骤,如下 下标、数组大小
        elementData[size++] = e;                                                 //实际存入数组中
        return true;        
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static int calculateCapacity(Object[] elementData, int minCapacity) {//检查数组下标
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                  //首次返回1
            return Math.max(DEFAULT_CAPACITY, minCapacity);                      //int DEFAULT_CAPACITY=10
        }
        return minCapacity;                                                      //后续返回当前值
    }

    private void ensureExplicitCapacity(int minCapacity) {                       //检查是否需要扩容数组
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)                                //当前下标是否大于数组已有长度
            grow(minCapacity);                                                  //自动扩容
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);            //拷贝数组,增加长度
    }

这就是ArrayList的添加元素的方法,通过必要的检查和扩容数组,下标从0开始自增,下标和元素一一对应存储在数组中。

这个类是不同步的,非线程安全的。

映射Map

将键映射到值的数据结构。Map不能包含重复的键; 每个键最多可以映射一个值。

Java中的Map是怎么实现的?

我们通过查看Map的实现类,熟悉一下Map

我们比较熟悉的HashMap、Hashtable、treeMap

Java中HashMapt的添加元素方法,简要分析

     package java.util.HashMap;  
     static final float DEFAULT_LOAD_FACTOR = 0.75f;                    //在构造函数中未指定时使用的加载因子

     static class Node<K,V> implements Map.Entry<K,V> {                //感觉是一个具有键值的链表
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    ......  //里面有一些方法getKey、getValue、toString、setValue
    }
     public HashMap() {                                                //构造函数
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {                               //获取Key的哈希值
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //调用key的对象哈希值,>>>为无符号右移运算符
    }

//第一个参数:Key的哈希值。第二个参数:key。第三个参数:值。
//第四:默认为true,改变key所映射的值。第五个参数:默认为false,哈希表已经创建。
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)          //transient Node<K,V>[] table;
            n = (tab = resize()).length;                                //resize()是初始化或加倍表格大小
        if ((p = tab[i = (n - 1) & hash]) == null)                 //链表数组是否为空
            tab[i] = newNode(hash, key, value, null); //创建具有保存键值的链表并保存数据进去,但是最后一个为null也就不是链表了
        else {                                                      //发生哈希冲突
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;                                             //让e非空
            else if (p instanceof TreeNode)                    //红黑树
                e = ((TreeNode<K,V>)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                //e非空,更改Node对象的值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)                                        //Node数组不够了
            resize();                                                  //扩容
        afterNodeInsertion(evict);                                     //默认true
        return null;
    }

看起来就很复杂,但是也比较容易弄懂,通过一个Node对象存储键值对 和哈希值,创建一个Node数组,假如Node数组为空则创建数组(扩容),假如没有发生哈希冲突,则创建Node对象存入数据;假如发生哈希冲突,则依此判断键值对是否改变,是否红黑树,否则就迭代链表。 java的树(TreeMap)是怎么实现的?

集合Set

不包含重复元素的集合。更明确的说法是,集合不包含相同元素e1和e2,使得e1.equals(E2)为真,并且至多一个null元素。

Java中的Set是怎么实现的?

我们看一下Set接口的实现类

我们通过比较熟悉的HashSet熟悉一下Set接口,同样的我们先看看添加元素方法

    package java.util.HashSet;
    public HashSet() {                //构造方法
        map = new HashMap<>();        //创建一个hashMap保存元素
    }

    private static final Object PRESENT = new Object();//与后面Map中的对象值关联的虚拟值
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;              //只传递Key,不传递值
    }

    //后面map.put(e,obj)的实现,可以看前面map的详细介绍

我们可以知道,HashSet利用到HashMap类,在创建Set对象的时候,也创建了HashMap对象,add添加元素方法,只传递Key进去和一个共同对象,后面生成哈希值,存储到Node节点中都由HashMap实现。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 基于 SpringCloud 微服务架构的广告系统(第一部分:eureka、zuul、通用模块)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    营琪
  • Java的基础程序设计结构(Java学习-1)

    注释就是方便自己或者别人阅读代码,绝大多数的程序语言都有注释这个功能,大部分的注释命令都是相同的或者想通的,

    营琪
  • 算法:哈希表HashTable-理论

    哈希表,我们平时好像用到的不多,使用HashMap的时候,才间接的使用到了,在信息安全领域用到的比较多(文件效验、数字签名),下面我们先来看看哈希函数。

    营琪
  • 面试 | Java8 HashMap原理

    基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化。

    Spark学习技巧
  • 面试必备:HashMap源码解析(JDK8)

    在分析jdk1.8后的HashMap源码时,发现网上好多分析都是基于之前的jdk,而Java8的HashMap对之前做了较大的优化,其中最重要的一个优化就是桶中...

    搜云库技术团队
  • Java 集合源码分析(一)HashMap

    附:更这个系列感觉自己像是又挖了一个坑?,不过趁自己刚好工作不太忙,有空闲期,静下心来研究学习源码也是一件很值得做的事,自己尽量会把这个坑填完?。

    希希里之海
  • HashMap源码剖析

    HashMap是大家常用的基于哈希表的Map接口实现,这里解说的是JDK1.8的代码,在介绍它之前,我们先来看看编写HashMap代码的是哪几位大牛。

    java达人
  • 90%面试都会问到的知识点,你看会吗?

    HashTable:线程安全,每个方法都加了 synchronized 修饰。类似 Collections.synchronizedMap(hashMap)

    好好学java
  • JDK源码分析-HashMap(1)

    HashMap 是 Java 开发中最常用的容器类之一,也是面试的常客。它其实就是前文「数据结构与算法笔记(二)」中「散列表」的实现,处理散列冲突用的是“链表法...

    WriteOnRead
  • HashMap,HashTable,ConcurrentHashMap面试总结!!!

    HashTable:线程安全,每个方法都加了 synchronized 修饰。类似 Collections.synchronizedMap(hashMap)

    用户5224393

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动