Java集合框架-HashMap
2021-05-29 07:00
标签：tac 基本 分布 wrap 增强for循环 uid 线程 rabl 方便 目录 HashMap 1 HashMap引入 2 HashMa数据结构 1、HashMap概述 2、HashMap在JDK1.8以前数据结构和存储原理 3、JDK1.8后HashMap的数据结构 4、HashMap的属性 3 HashMap的源码分析 1、HashMap的层次关系与继承结构 2、HashMap类的属性 3、HashMap的构造方法 4、常用方法 4 总结 迭代器 泛型 Collections工具类 1、Collectios概述 2、排序操作 3、查找、替换操作 4、同步控制 5、Collesction设置不可变集合 Vevtor和Stack 1 Vector 1、Vector概述 2、Vector源码分析 3、核心方法 2 Stack 3 总结Vector和Stack Map接口专门处理键值映射数据的存储，可以根据键实现对值的操作。 HashMap是基于哈希表的Map接口实现的，它存储的是内容是键值对 链表散列 通过数组和链表结合在一起使用，就叫做链表散列。这其实就是hashmap存储的原理图。 HashMap的数据结构和存储原理 HashMap内部有一个entry的内部类，其中有四个属性，我们要存储一个值，则需要一个key和一个value，存到map中就会先将key和value保存在这个Entry类创建的对象中。 通过entry对象中的hash值来确定将该对象存放在数组中的哪个位置上，如果在这个位置上还有其他元素，则通过链表来存储这个元素。 Hash存放元素的过程 上图展示了HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。 HashMap的实例有两个参数影响其性能。 capacity译为容量代表的数组的容量，也就是数组的长度，同时也是HashMap中桶的个数。默认值是16。 通过一张HashMap的数据结构图来分析： 【HashMap继承结构】 【实现接口】 【HashMap()】： 【HashMap(int)】 【HashMap(int,float)】 【HashMap(Map extends K, ? extends V> m)】 【put(K key,V value)】 【putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)】 HashMap并没有直接提供putVal接口给用户调用，而是提供的put函数，而put函数就是通过putVal来插入元素的。 【get(Object key)】 【getNode(int hash,Pbject key)】 HashMap并没有直接提供getNode接口给用户调用，而是提供的get函数，而get函数就是通过getNode来取得元素的。 【resize方法】 进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。 1. 要知道hashMap在JDK1.8以前是一个链表散列这样一个数据结构，而在JDK1.8以后是一个数组加链表加红黑树的数据结构。 所有实现了Collection接口的容器类都有一个iterator方法用以返回一个实现Iterator接口的对象 Iterator对象称作为迭代器，用以方便的对容器内元素的遍历操作，Iterator接口定义了如下方法： 方法1：通过迭代器Iterator实现遍历 方法2：增强for循环 泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数。 通过泛型 ， JDK1.5使用泛型改写了集合框架中的所有接口和类 ？ 通配符： Java提供了一个操作Set、List和Map等集合的工具类：Collections，该工具类提供了大量方法对集合进行排序、查询和修改等操作，还提供了将集合对象置为不可变、对集合对象实现同步控制等方法。 Collectons提供了多个synchronizedXxx()方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。 锁机制：对象锁、方法锁、类锁 1. Vector是一个可变化长度的数组 Vector的继承关系和层次结构和ArrayList中的一模一样 构造方法作用： 【Vector()：空构造】 【Vector(int)】 【ector(int，int)】 【Vector(Collection extends E> c)】 这个就是在每个方法上比arrayList多了一个synchronized，其他都一样。 Vector的子类Stack，我们学过数据结构都知道，这个就是栈的意思。那么该类就是跟栈的用法一样 【Vector总结】 Java集合框架-HashMap 标签：tac 基本 分布 wrap 增强for循环 uid 线程 rabl 方便 原文地址：https://www.cnblogs.com/koudada/p/14773246.html
HashMap
1 HashMap引入
最常用的实现类是HashMap。2 HashMa数据结构
1、HashMap概述
2、HashMap在JDK1.8以前数据结构和存储原理
?
?
?
3、JDK1.8后HashMap的数据结构
?
4、HashMap的属性
初始容量：哈希表中桶的数量
加载因子：哈希表在其容量自动增加之前可以达到多满，的一种尺度
当哈希表中条目数超出了当前容量*加载因子(其实就是HashMap的实际容量)时，则对该哈希表进行rehash操作，将哈希表扩充至两倍的桶数。
Java中默认初始容量为16，加载因子为0.75。static final int DEFAULT_INITIAL_CAPACITY = 1 // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。static final int DEFAULT_INITIAL_CAPACITY = 1 // aka 16
?
3 HashMap的源码分析
1、HashMap的层次关系与继承结构
?
public class HashMap
2、HashMap类的属性
public class HashMap
3、HashMap的构造方法
//看上面的注释就已经知道，DEFAULT_INITIAL_CAPACITY=16，DEFAULT_LOAD_FACTOR=0.75
//初始化容量：也就是初始化数组的大小
//加载因子：数组上的存放数据疏密程度。
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 初始容量不能小于0，否则报错
if (initialCapacity )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始容量不能大于最大值，否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 填充因子不能小于或等于0，不能为非数字
if (loadFactor Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 初始化填充因子
this.loadFactor = loadFactor;
// 初始化threshold大小
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map extends K, ? extends V> m) {
// 初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
// 将m中的所有元素添加至HashMap中
putMapEntries(m, false);
}
4、常用方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
public V get(Object key) {
Node
在resize前和resize后的元素布局如下:
?
4 总结
2. 通过源码的学习，hashMap是一个能快速通过key获取到value值得一个集合，原因是内部使用的是hash查找值得方法。迭代器
Set keys=dogMap.keySet(); //取出所有key的集合
Iterator it=keys.iterator(); //获取Iterator对象
while(it.hasNext()){
String key=(String)it.next(); //取出key
Dog dog=(Dog)dogMap.get(key); //根据key取出对应的值
System.out.println(key+"\t"+dog.getStrain());
}
for(元素类型t 元素变量x : 数组或集合对象){
引用了x的java语句
}
泛型
?
?
Collections工具类
这个类不需要创建对象，内部提供的都是静态方法。1、Collectios概述
?
2、排序操作
static void reverse(List> list):
反转列表中元素的顺序。
static void shuffle(List> list) :
对List集合元素进行随机排序。
static void sort(List
3、查找、替换操作
static
4、同步控制
static
5、Collesction设置不可变集合
emptyXxx()
返回一个空的、不可变的集合对象，此处的集合既可以是List，也可以是Set，还可以是Map。
ingletonXxx():
返回一个只包含指定对象（只有一个或一个元素）的不可变的集合对象，此处的集合可以是：List，Set，Map。
unmodifiableXxx():
返回指定集合对象的不可变视图，此处的集合可以是：List，Set，Map。
Vevtor和Stack
对象锁就是方法锁：就是在一个类中的方法上加上synchronized关键字，这就是给这个方法加锁了。
类锁：锁的是整个类，当有多个线程来声明这个类的对象的时候将会被阻塞，直到拥有这个类锁的对象被销毁或者主动释放了类锁。这个时候在被阻塞住的线程被挑选出一个占有该类锁，声明该类的对象。其他线程继续被阻塞住。例如：在类A上有关键字synchronized，那么就是给类A加了类锁，线程1第一个声明此类的实例，则线程1拿到了该类锁，线程2在想声明类A的对象，就会被阻塞。
现在使用的是方法锁。1 Vector
1、Vector概述
?
2. Vector增加长度通过的是capacity和capacityIncrement这两个变量，目前还不知道如何实现自动扩增的，等会源码分析
3. Vector也可以获得iterator和listIterator这两个迭代器，并且他们发生的是fail-fast，而不是failsafe，注意这里，不要觉得这个vector是线程安全就搞错了
4. Vector是一个线程安全的类，如果使用需要线程安全就使用Vector，如果不需要，就使用arrayList
5. Vector和ArrayList很类似，就少许的不一样，从它继承的类和实现的接口来看，跟arrayList一模一样。2、Vector源码分析
1. 初始化存储元素的容器，也就是数组，elementData，
2. 初始化capacityIncrement的大小，默认是0，这个的作用就是扩展数组的时候，增长的大小，为0则每次扩展2倍3、核心方法
2 Stack
class StackE> extends 1 VectorE> {}
?
3 总结Vector和Stack
1. Vector线程安全是因为它的方法都加了synchronized关键字
2. Vector的本质是一个数组，特点能是能够自动扩增，扩增的方式跟capacityIncrement的值有关
3. 它也会fail-fast，还有一个fail-safe两个的区别在下面的list总结中会讲到。
【Stack的总结】
1. 对栈的一些操作，先进后出
2. 底层也是用数组实现的，因为继承了Vector
3. 也是线程安全的