Java集合-Collection & Map

这篇具有很好参考价值的文章主要介绍了Java集合-Collection & Map。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

概念

1.集合主要是两组:单列集合(Collection) , 双列集合(Map)
2.Collection 接口有两个重要的子接口 List ,Set . 他们的实现子类都是单列集合
Java集合-Collection & Map
3.Map 接口的实现子类 是双列集合,存放的 K-V

Iterable

单列集合的顶级接口,含有Iterator()方法,主要用于遍历Collection集合中的元素
Collection的所有实现类都有Iterator()方法,返回值为调用该方法的实现类对象
1.常用方法:

Iterator iterator = collection.iterator();//获取集合的迭代器
iterator.hasNext();//是否存在下一个元素,仅判断
iterator.next();//返回集合中的当前元素,初始指向集合中第一个元素,调用一次,指针往下挪一位
iterator.remove();//移除集合中的当前元素,初始指向集合中第一个元素,调用一次,指针往下挪一位

2.常用一下方法遍历集合
idea快捷键: itit | itco

Iterator<Integer> iterator = collection.iterator();
while (iterator.hasNext()){
   System.out.println(iterator.next());
}

遍历完后,不可在调用iterator.next(),会抛出NoSuchElementException异常
如果还想使用,在使用collection.iterator()获取一个迭代器即可

3.增强for循环就是简单版本的iterator(),底层是迭代器,集合,数组都可以使用

for (Object object: collection) {
   System.out.println(object);
}

Collection接口

Collection 接口常用方法:

collection.add(1);//添加一个元素
collection.addAll();//添加一个集合中的所有元素
collection.remove();//删除指定元素
collection.removeAll();//删除传入集合中的所有元素
collection.clear();//清空集合
collection.contains();//判断集合是否含有传入元素
collection.containsAll();//判断集合是否包含传入集合的所以有元素
collection.size();//集合大小
collection.isEmpty();//判断集合是否为空

List接口

List中的元素是有序的,存入和取出顺序一致,且元素可重复
List中所有元素都有索引(从0开始),可以根据索引取元素
1.List中的常用方法

list.get(index);//获取指定索引的元素
list.indexOf(item);//获取指定元素首次出现的索引
list.lastIndexOf(item);//获取指定元素最后出现的索引
list.add(index,item);//在index 和 index-1 之间添加一个元素
list.remove(index);//根据指定索引删除元素
list.set(index,item);//替换指定索引元素
list.subList(l,r);//返回 l<= i < r之间的元素

2.遍历List的方法
1.简单for循环
2.增强for循环
3.iterator

ArrayList

可以存放一或多个null值,list.add(null);
有数组实现数据存储
线程不安全

		ArrayList list = new ArrayList();
		//使用 for 给 list 集合添加 1-10 数据
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }
		//使用 for 给 list 集合添加 11-15 数据
        for (int i = 11; i <= 15; i++) {
            list.add(i);
        }
        list.add(100);
        list.add(200);
        list.add(null);

执行流程 && 底层源码分析:
扩容机制:

transient Object[] elementData;//内部维护的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组
private static final int DEFAULT_CAPACITY = 10;
1.
//无参构造创建
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  //判断当前数组大小是否够用,不够进行扩容处理
        elementData[size++] = e;
        return true;
    }

3.
    private void ensureCapacityInternal(int minCapacity) {//此时minCapacity为1 ,是size+1传递过来的size初始为0
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)//判断内部数组长度大于还是小于10);
    }
4.1
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判断维护数组是否为空数组
        	//DEFAULT_CAPACITY为10
            return Math.max(DEFAULT_CAPACITY, minCapacity);//返回10和原数组大小较大的一个
        }
        //首次长度初始化为10
        return minCapacity;
    }
4.2
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//记录集合被修改的次数
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//如果外部数组长度大于内部数组长度,则扩容
            grow(minCapacity);//扩容
}
5.
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;//oldCapacity 为 1
        int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//无参构造创建,首次扩容为10
        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);//将旧数组拷贝到新,如果新数组的长度超过原数组的长度,其余用默认值填充
    }
6.一步一步返回,如此循环,满了就1.5本扩容,直到MAX_ARRAY_SIZE ,如果使用有参构造传入value,那么,就按照传入的值1.5倍扩容

//如果是有参构造,就是将长度初始化了,内部数组为自定义长度的数组
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];//内部数组成了自定义长度的数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        }
    }

Vector

1.Vector是线程同步的即线程安全的,所有的方法都带有synchronized
2.无参构造创建: 默认内部数组为10 ,之后2倍扩容,有参构造指定长度,按指定2倍长度扩容

1.Vector底层也是一个对象数组
protected Object[] elementData;

扩容源码分析:无参
1.    
public Vector() {
   this(10);//默认内部数组初始大小
}
2.
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
3.
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        this.elementData = new Object[initialCapacity];//创建初始值为10的内部数组
        this.capacityIncrement = capacityIncrement;
    }
4.第一次add
protected int elementCount;//数组中有效元素个数

    public synchronized boolean add(E e) {
        modCount++;//记录修改次数
        ensureCapacityHelper(elementCount + 1);//
        elementData[elementCount++] = e;
        return true;
    }
4.1	
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)//数组有效元素长度 - 数组总长度
            grow(minCapacity);
    }
4.2由于数组初始长度为10,add 10次后进入grow方法
protected int capacityIncrement;//容器自增量,可以在创建集合是设置,为构造器第二个参数
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);//默认自增量为0,所以默认扩容两倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

其他:
有参:
指定初始长度
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
指定初始长度和每次扩容量
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

LinkedList

1.LinkedList底层维护一个双向链表,更具索引获取值时,索引从0开始
2.内部维护了一个静态内部类

    private static class Node<E> {
        E item;//当前节点的值
        Node<E> next;//指向下一个节点
        Node<E> prev;//指向前一个节点

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//
            this.next = next;
            this.prev = prev;
        }
    }

简单操作:

        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);

LinkedList初始化及CURD源码分析:

几个重要参数:
transient int size = 0;//链表长度
transient Node<E> first;//第一个结点位置
transient Node<E> last;//最后一个结点位置
protected transient int modCount = 0;//此列表在结构上被修改的次数,防止线程安全问题,如果该字段的值意外变化,迭代器(或列表迭代器)将抛出ConcurrentModificationException异常来响应next、remove、previous、set或add操作。这提供了快速失败的行为,

	//无参构造初始化
    public LinkedList() {
    }
增加:
1.  
	public boolean add(E e) {
        linkLast(e);
        return true;
    }
2.
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
调用静态节点类的构造方法
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;//给当前节点赋值
            this.next = next;//增加节点的next指向下一个节点
            this.prev = prev;//prev指向上一个结点
        }  
删除:
        1.linkedList.removeFirst();//删除头节点
        调用核心方法:private E unlinkFirst(Node<E> f)
        2.linkedList.removeLast();//删除尾节点
        调用核心方法:private E unlinkLast(Node<E> l) 

上述23.linkedList.remove();//底层调用的是removeFirst
        4.linkedList.remove(new Integer(4));//删除指定对象节点
        5.linkedList.remove(3);//更具索引删
上述3个方法的核心都是在E unlink(Node<E> x)上进行修改或加以限制,
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
		//重新指定删除结点的下一个节点的prev指向
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
		//重新指定删除结点的上一个节点的next指向
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
查找:
		1.linkedList.get(1);//返回指定索引节点保存的数据值
        2.linkedList.getLast();
        3.linkedList.getFirst();
更改:
linkedList.set(index,value);更具指定索引,修改对应的节点数据

ArrayList 和 LinkedList 比较

查找多,用ArrayList
修改多,用LinkedList

Set

无序(添加和取出元素顺序,但取出顺序固定不变),没索引.
不允许有重复元素

遍历方法:
迭代器
增强for循环
不能用索引方式

HashSet

1.HashSet底层实际上时HashMap
2.第一次添加是内部的table数组扩容到16,再次扩容临界值是16 * 加载因子(默认0.75) 为12,下次扩容临界值是 2 乘以16 乘以0.75 为24
3.在Java8中如果一条链表的元素个数 达到 8 也就是>=7 且table数组大小大于64,就会进行树化(红黑树).否则仍采用数组扩容机制

1.HashSet底层是HashMap
2.添加元素时,先计算得到hash值会转成索引值,找到存储数据表table,若果索引位置没有元素则直接加入,若已经存放有元素则调用equals比较,为true,就放弃添加,不相同,再判断 p 是不是一颗红黑树, 如果是一颗红黑树,就调用 putTreeVal , 来进行添加.不是红黑树,依次和该链表的每一个元素比较后,都不相同, 则加入到该链表的最后.

        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("java");
        hashSet.add("php");
源码分析:
	无参构造初始化
    public HashSet() {
        map = new HashMap<>();
    }
1.添加 "java"
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
2.
    public V put(K key, V value) {
        return putVal(hash(key)//计算哈希值, key, value, false, true);
    }
2.1
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
3.进入putVall方法
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 语句表示如果当前 table 是 null, 或者 大小=0
        //table 就是 HashMap 的一个数组,类型是 Node[]
		//if 语句表示如果当前 table 是 null, 或者 大小=0
		//就是第一次扩容,到 16 个空间.
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;//刚开始tab为空,进入resize()方法进行第一次扩容
//(1)根据 key,得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
//并把这个位置的对象,赋给 p
//(2)判断 p 是否为 null
//(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        //如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样
		//并且满足 下面两个条件之一:
		//(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象
		//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同
		//就不能加入
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //再判断 p 是不是一颗红黑树, 
                //如果是一颗红黑树,就调用 putTreeVal , 来进行添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//(1) 依次和该链表的每一个元素比较后,都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后,立即判断 该链表是否已经达到 8 个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意,在转成红黑树时,要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立,先 table 扩容. // 只有上面条件不成立时,才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中,如果有相同情况,就直接 break
                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;//返回null代表添加成功
    }

3.1 第一次扩容
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {//false
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold//false
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults//初始化
            newCap = DEFAULT_INITIAL_CAPACITY;//第一次扩容大小: 16,默认初始大小
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//当数据大小为0.75 * 16时再次扩容
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;//赋值,正真扩容!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;//返回
    }

LinkedHashSet

1.LinkedHashSet使用hashcode值来决定元素的存储位置,使用双向链表维护元素的次序,元素以插入顺序保存.(加入和取出元素顺序一致)
2.LinkedHashSet底层是一个LinkedHashMap(是HashMap的子类),底层维护一个数组加双向链表
3.LinkedHashSet不能插入重复元素
4.第一次添加时将数组 table(table的类型是HashMap N o d e [ ] ) 扩容到 16 , 存放的结点类型是 L i n k e d H a s h m a p Node[]) 扩容到 16 ,存放的结点类型是LinkedHashmap Node[])扩容到16,存放的结点类型是LinkedHashmapEntry
LinkedHashmap$Entry

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;//双向链表记录的前后结点
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

常用方法:

Map

Set 中 k-v k是添加值,v是present常量,只用了k
Map 中 k - v 都由用户添加
1.Map与Collection并列存在。用于保存具有映射关系的数据:Key-Value(双列元素)
2.Hap中的 key 和 value 可以是任何引用类型的数据,会封装到HashMap$Node对象中
3. Map中的key不允许重复,原因和HashSet一样,前面分析过源码。
4. Map中的value可以重复,如果key相同,则覆盖之前的value
5. Map 的 key 可以为 null, value 也可以为 null ,注意 key 为 null,
6. 常用 String 类作为 Map 的 key
7. key 和 value 之间存在单向一对一关系,即通过指定的 key 总能找到对应的 value

常用方法:

Map map = new HashMap();
map.put(key, value);//替换-> 一会分析源码
map.remove(key)根据键删除映射关系
map.get(key)根据键获取值
map.size();获取元素个数
map.containsKey(key)是否包含指定key
map.isEmpty();判断个数是否为空 
map.clear();清空集合

遍历:

//第一组: 先取出 所有的 Key , 通过 Key 取出对应的 Value
Set keyset = map.keySet();
//(1) 增强 for
System.out.println("-----第一种方式-------");
for (Object key : keyset) {
System.out.println(key + "-" + map.get(key));
}
//(2) 迭代器
System.out.println("----第二种方式--------");
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}

//第二组: 把所有的 values 取出
Collection values = map.values();
//这里可以使用所有的 Collections 使用的遍历方法
//(1) 增强 for
System.out.println("---取出所有的 value 增强 for----");
for (Object value : values) {
System.out.println(value);
}
//(2) 迭代器
System.out.println("---取出所有的 value 迭代器----");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
Object value = iterator2.next()
System.out.println(value);
}

//第三组: 通过 EntrySet 来获取 k-v
Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>
//(1) 增强 for
System.out.println("----使用 EntrySet 的 for 增强(第 3 种)----");
for (Object entry : entrySet) {
//将 entry 转成 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
//(2) 迭代器
System.out.println("----使用 EntrySet 的 迭代器(第 4 种)----");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Object entry = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
//向下转型 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
}

HashMap

jdk8: 底层是数组+链表+红黑树
数组长度大于64 且 链表长度大于8 该节点的链表树化

  1. HashMap底层维护了Node类型的数组table,默认为null
    2)当创建对象时,将加载因子(loadfactor)初始化为0.75.
    3)当添加key-val时,通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,
    如果没有元素直接添加。如果该索引处有元素,继续判断该元素的key是否和准备加入的key相等,如果相等,则直接替换val;如果不相等需要判断是树结构还是链表结构,做出相应处理。如果添加时发现容量不够,则需要扩容。
    4)第1次添加,则需要扩容table容量为16,临界值(threshold)为12.,以后再扩容,则需要扩容table容量为原来的2倍,临界值为原来的2倍,即24,依次类推.
    6)在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),粗table的大小>= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)

1.k-v最后是 HashMap.Node node = newNode(hash,key,value,null)
2.k-v为了方便程序员的遍历,创建了EntrySet集合,该集合存放的元素的类型Entry,而一个Entry对象就有k ,v EntrySet<Entry<K,V>>即: transient Set<Map. Entry<K, V>> entrySet;
3. entrySet中,定义的类型是Map.Entry ,但是实际上存放的还是 HashMap.Node,这是因为 HashMap.Node implements Map.Entry
4.当把 HashMap.Node 对象存放到entrySet 就方便我们的遍历,因为 Map.Entry 提供了重要方法K getKey V getValue();
5.实际上就是把所有HashMap$Node转成Entry,然后把所有Entry放到EntrySet中(存放的是地址,不是实际数据),方便程序员遍历,EntrySet中的数据实际指向的是类型为HashMap Node[] 的table表中的数据(存放的是地址,不是实际数据)

内部节点
//实现implements Map.Entry<K,V>接口
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }//getKey
        public final V getValue()      { return value; }//getValue
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
EntrySet 中包含所有Entry,但是不能直接获取Entry对象,可以使用增强for循环遍历
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {......}

所以还提供了直接获取所有key的内部类
final class KeySet extends AbstractSet<K> {.......}
以及直接获取所有Value的内部类
final class Values extends AbstractCollection<V> {......}

解析 hashMap.put(key,value)
扩容等机制和HashSet基本一样文章来源地址https://www.toymoban.com/news/detail-485051.html

1.
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
2.
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)
        //第一次扩容
            n = (tab = resize()).length;
            //hash值对应的数组索引为空,直接放入
        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;//相等就记录,为后面对应键的新值覆盖旧值做铺垫
            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//不为空,说明添加的键重复
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;//新值覆盖旧值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

细致分析
// 1. 执行构造器 new HashMap()
        //初始化加载因子 loadfactor = 0.75
        //HashMap$Node[] table = null
        //2. 执行 put 调用 hash 方法,计算 key 的 hash 值 (h = key.hashCode()) ^ (h >>> 16)
        public V put(K key, V value) {//K = "java" value = 10
            return putVal(hash(key), key, value, false, true);
        }
        3. 执行 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;//辅助变量
//如果底层的 table 数组为 null, 或者 length =0 , 就扩容到 16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
//取出 hash 值对应的 table 的索引位置的 Node, 如果为 null, 就直接把加入的 k-v
//, 创建成一个 Node ,加入该位置即可
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;//辅助变量
// 如果 table 的索引位置的 key 的 hash 相同和新的 key 的 hash 值相同,
// 并 满足(table 现有的结点的 key 和准备添加的 key 是同一个对象 || equals 返回真)
// 就认为不能加入新的 k-v
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)//如果当前的 table 的已有的 Node 是红黑树,就按照红黑树的方式处理
                            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);
//加入后,判断当前链表的个数,是否已经到 8 个,到 8 个,后
//就调用 treeifyBin 方法进行红黑树的转换
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash && //如果在循环比较过程中,发现有相同,就 break,就只是替换 value
                                ((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; //替换,key 对应 value
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;//每增加一个 Node ,就 size++
            if (++size > threshold[12-24-48])//如 size > 临界值,就扩容
                resize();
            afterNodeInsertion(evict);
            return null;
        }
        5. 关于树化(转成红黑树)
//如果 table 为 null ,或者大小还没有到 64,暂时不树化,而是进行扩容. //否则才会真正的树化 -> 剪枝
        final void treeifyBin(Node<K,V>[] tab, int hash) {
            int n, index; Node<K,V> e;
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize();
        }
*/
    }
}

到了这里,关于Java集合-Collection & Map的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • java Collection集合使用笔记

    它是单例集合的最顶层接口,它表示一组对象,这些对象也称之为Collection的元素 JDK不提供此接口任何直接实现,但提供更具体的子接口(如: List 和 Set )实现 创建Collection集合对象的方法: 多态的形式 具体的实现类: ArrayList Iterator迭代器,Collection集合的专用遍历方式 I

    2024年02月11日
    浏览(47)
  • Java笔记(15) Collection集合-->List集合

    集合的理解和好处 数组一旦定义,长度即固定,不能修改。要添加新元素需要新建数组,然后循环拷贝,非常麻烦 集合可以动态保存任意多个对象,使用比较方便 提供饿了一系列方便的操作对象的方法:add、remove、set、get等 使用集合添加、删除新元素的示意代码,简洁明了

    2023年04月14日
    浏览(46)
  • Java笔记(16) Collection集合-->Set集合-->HashSet

    Set是无序集合(添加和取出的顺序不一致,但取出的顺序是固定的),没有索引 不允许重复元素,所以最多包含一个null JDK API中Set接口的实现类有: Abstract, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet Set接口和List接口一

    2023年04月15日
    浏览(58)
  • 进阶JAVA篇- Collection 类的常用的API与 Collection 集合的遍历方式

    目录         1.0 Collection 类的说明         1.1 Collection 类中的实例方法         2.0 Collection 集合的遍历方式(重点)         2.1 使用迭代器( Iterator )进行遍历         2.2 使用增强型 for 循环进行遍历         2.3 使用 Java 8的 Stream API 进行遍历(使用 Lambda 表达式进

    2024年02月08日
    浏览(46)
  • 【从零开始学Java66】讲解Java集合中的Collection体系

    本文将为大家详细讲解Java中的Collection体系,这是我们进行开发时经常用到的知识点,也是大家在学习Java中很重要的一个知识点,更是我们在面试时有可能会问到的问题。 文章较长,干货满满,建议大家收藏慢慢学习。文末有本文重点总结,主页有全系列文章分享。技术类问

    2024年02月06日
    浏览(40)
  • 49天精通Java,第23天,Java集合,Collection接口,Iterator接口

    大家好,我是哪吒。 在Java类库中,集合类的基类是Collection接口。

    2023年04月11日
    浏览(41)
  • 从零开始学习 Java:简单易懂的入门指南之Collection集合及list集合(二十一)

    1.1数组和集合的区别 相同点 都是容器,可以存储多个数据 不同点 数组的长度是不可变的,集合的长度是可变的 数组可以存基本数据类型和引用数据类型 集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类 1.2集合类体系结构 1.3Collection 集合概述和使用 Collec

    2024年02月10日
    浏览(39)
  • 【JAVA学习笔记】 56 - 开发中如何选择集合实现类,以及Collection工具类

    https://github.com/yinhai1114/Java_Learning_Code/blob/main/IDEA_Chapter14/src/com/yinhai/Collections_.java 目录 项目代码 Collections工具类 一、Collections工具类介绍 1.排序操作: (均为static方法) 2.查找、替换 在开发中,选择什么集合实现类,主要取决于业务操作特点,然后根据集合实现类特性进行 选择

    2024年02月06日
    浏览(40)
  • 【JAVA学习笔记】53 - 集合-List类及其子类Collection、ArrayList、LinkedList类

    https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/collection_ https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter14/src/com/yinhai/list_ 目录 项目代码 集合 一、引入 数组 集合 二、集合的框架体系 单列集合        双列集合        Collection类 一、Collection类接

    2024年02月06日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包