Mushroom Notes
kinoko
2023-12-16
目录

数据结构

# 数据结构

# 链表

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; }
        public final V getValue()      { return value; }
        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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 平衡二叉树

  • 平衡二叉树是高度平衡的，当执行插入或者删除操作时，只要左右子树高度差超过1时，就要通过旋转来保持平衡，而旋转是非常耗时的。
  • 由此可见，平衡二叉树适用于元素增删较少，而查找较多的场景。
  • 由于维护高度平衡的代价较大，故而平衡二叉树实际的应用不多，更多时候会选择更加高效的红黑树。

# 红黑树

  • 红黑树是特殊的二叉查找树，在每个节点上有一个存储位表示节点的颜色，可以是红或黑（非红即黑）。
  • 红黑树是一种弱平衡二叉树，相对于要求严格的平衡二叉树来说，它的旋转次数相对较少。
  • 对于查询，插入，删除都较多的情况下，我们可以使用红黑树达到整体性能的提升。
  • 最长路径不超过最短路径的两倍

红黑树不是高度平衡的，它的平衡是通过“红黑规则”进行实现的。

规则如下：

1.每一个节点或是红色的，或者是黑色的。boolean  red = false;
2.根节点必须是黑色
3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的；
4.不能出现两个红色节点相连的情况
5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。
6.新加入的节点是红色的，如果加入后不满足红黑规则，需要进行旋转或变色。

# 各种数据结构的特点和作用是什么样的

  • 队列：先进先出。
  • 栈：先进后出。
  • 数组：内存连续区域，查询快，增删慢。
  • 链表：元素是游离的，查询慢，增删。
  • 二叉树：永远只有一个根节点, 每个结点不超过2个子节点的树。
  • 查找二叉树：小的左边，大的右边，但是可能树很高，查询性能变差。
  • 平衡查找二叉树：让树的高度差不大于1，查询效率高，但是维护平衡代价大。
  • 红黑树（就是基于红黑规则实现了自平衡的排序二叉树）综合性能好。

# Collection集合

集合结构
image.png
共性方法

方法名称 说明
public   boolean add(E   e) 把给定的对象添加到当前集合中
public   void clear() 清空集合中所有的元素
public   boolean remove(E   e) 把给定的对象在当前集合中删除
public   boolean contains(Object   obj) 判断当前集合中是否包含给定的对象
public   boolean isEmpty() 判断当前集合是否为空
public   int size() 返回集合中元素的个数。
public   Object[] toArray() 把集合中的元素，存储到数组中

# 迭代器并发修改异常

当使用迭代器遍历集合元素时，使用了当前遍历的集合对象对集合进行了增删操作。两个不同的对象同时操作同一组数据，就会产生并发修改异常异常java.util.ConcurrentModificationException。

如何避免？

迭代器提供了一个remove()方法来进行集合元素的删除，使用这个方法对集合进行操作，就可以避免出现两个不同对象操作同一组数据的情况，从而避免并发修改异常。

但是迭代器没有提供增加元素的方法，因为迭代器底层是通过计数器来实现指针的移动，若是在已遍历的区间添加了元素，就会打乱迭代的过程，所以迭代器不允许增添的操作。

底层实现

在迭代器实现类的next()方法中，会调用checkForComodification()方法判断是否被修改，modCount记录的是List集合添加元素的次数，expectedModCount记录的是迭代前List集合添加元素的次数，当迭代时发生list集合元素添加的话，就会抛出并发修改异常。

注意：迭代器是集合的内部类，可以直接调用集合方法和获取集合成员属性
private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount; // 创建迭代器时记录集合修改次数
		...
}
---------------------------------------
public E next() {
            checkForComodification();//检查方法
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
---------------------------------------
final void checkForComodification() {
            if (modCount != expectedModCount)//List集合修改的次数！=迭代前List集合修改的次数
                throw new ConcurrentModificationException();
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注意： 迭代器是用于遍历没有get方法的集合，如果有get方法，并且是有索引的集合，正常使用for循环就行。并且在JDK5以后就可以用增强for循环去替代迭代器，增强for的出现就是为了简化迭代器的语法，但是由于增强for循环的底层就是迭代器，所以一样不能在增强for循环里进行对集合进行增删的操作。

增强for遍历集合底层是迭代器，增强for遍历数组底层是普通for循环

# 泛型

泛型是jdk5引入的特性，它提供了编译时类型安全检测机制。

泛型的好处

  • 把运行期的问题提前到了编译期
  • 避免了强制类型转换

泛型的格式

  • <引用数据类型>
       尖括号里面可以任意书写，按照变量的定义规则即可，一般只写一个大写字母。
       比如：
  • <类型1,  类型2>
       指定多种泛型格式，多种类型之间用逗号隔开。
       比如：<K, V> Map<K,V>

泛型的使用

可以使用数据类型的地方就可以使用泛型代替

  • 定义在类后面（泛型类） ArrayList<T>
  • 定义在接口后面（泛型接口）  List<T>
  • 定义在方法申明上（泛型方法）public<T> void  show(T t) {  }

注意： 泛型没有重载和多态

# 类型通配符

?是类型通配符，在泛型中使用时被称为泛型通配符<?>

泛型通配符 <?> 是在使用泛型的时候，用来代表某种类型的符号。

泛型通配符的上下限

因为泛型是没有重载和多态的特性的，所以当需要使用继承的特性时，可以通过规定类型通配符的上下限来达到限制的作用。

格式

? super Car泛型只能是Car或者Car的父类，规定了下限

? extends Car泛型只能是Car或者Car的子类，规定了上限

# List接口

特点： 存跟取的顺序一致，有索引，允许存放重复的元素
**扩展：**线程安全的List集合

  • Vector： 通过同步锁锁住方法达到线程安全，由于效率太低，被淘汰
  • Collections.synchronizedList(List<T> list)： 通过同步代码块锁住调用方法的代码块，同样是效率太低
  • CopyOnWriteArrayList： 在面临写操作的时候，CopyOnWriteArrayList会先复制原来的数组并且在新数组上进行修改，最后再将原数组覆盖。如果写操作的过程中发生了线程切换，并且切换到读线程，因为此时数组并未发生覆盖，读操作读取的还是原数组。换句话说，就是读操作和写操作位于不同的数组上，因此它们不会发生安全问题。

# ArrayList

特点：

  • 底层数据结构是数组，需要连续的内存
  • 查询快，尾部增删快，其他部位的增删慢
  • 可以利用CPU缓存，局部性原理

底层源码分析JDK11：

ArrayList的底层是数组

transient Object[] elementData;// 底层数组
1

使用无参构造方法创建集合对象，将底层初始化为长度为0的默认数组

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
---------------------等价于
this.elementData = {};//目的是在给集合添加元素之前，尽可能的减少内存空间的占用
1
2
3
4
5
6

如果使用的是有参构造创建集合对象，则是将底层数组初始化为指定大小的数组

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);
        }
    }
1
2
3
4
5
6
7
8
9
10

元素添加操作以及扩容规则

扩容规则

  • 申请集合内存空间时，数组长度为0；
  • 当首次添加元素单个元素时，数组扩容为10；
  • 当集合中元素个数达到数组容量时，扩容为上一次容量的1.5倍；
  • 当调用addAll()时，会与默认容量做比较取最大值作为下一次扩容的容量；
public boolean add(E e) {
        modCount++;// 操作集合数据次数
        add(e, elementData, size);	// 类型，数组，集合元素个数
        return true;
    }
-----------------------------------
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)// 判断是否达到数组容量
            elementData = grow();// 达到则扩容
        elementData[s] = e;// 否则直接放入元素
        size = s + 1;// 元素+1（指针右移一位）
    }
-----------------------------------
private Object[] grow() {
        return grow(size + 1);
    }
private Object[] grow(int minCapacity) {
    	// 创建新数组，将旧数组复制到新数组
        return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
    }
-----------------------------------
private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);// 新容量为旧容量的1.5倍
    	// 判断新数组容量是否小于元素个数，基本只有首次添加元素才会进入这个if
        if (newCapacity - minCapacity <= 0) {
            // 若数组为默认数组，则是首次添加元素
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // 返回DEFAULT_CAPACITY默认容量10
                // 若是通过addAll()进入的此方法，会将默认容量与添加元素相比取最值
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
    	// 判断新数组容量是否小于最大容量
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# LinkedList

既可以当做队列也可以当做栈使用

特点：

  • 底层数据结构是双向链表，不需要连续的内存，内存占用大
  • 首尾增删快，随机查询慢

底层源码分析

数据结构是双向链表

transient Node<E> first;
transient Node<E> last;
------------------------
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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

添加元素，默认向尾部

public boolean add(E e) {
        linkLast(e);
        return true;
    }
--------------------------
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//否则让前一个节点的next指针指向新节点的地址
            l.next = newNode;
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 哈希表

在JDK1.7哈希表采用数组+链表实现。

从JDK8开始，对于哈希表的实现做了一些改进，通过数组 + 链表 + 红黑树 实现。

当经常发生哈希冲突(元素的哈希值相同) 时，链表长度将会变的非常长，逐一比较是否相同时，势必耗费大量时间降低性能。为此当链表元素超过8 个时，在JDK8中会将该链表转换为红黑树进行存储。目的在于减少比较次数，提高性能，以及预防DOS攻击。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//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; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
		
    	....
}
-------------------------
transient Node<K,V>[] table;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# Set接口

特点：

存跟取的顺序不一致，无索引，不允许存放重复的元素

# HashSet

特点：

  • 存储的元素是无序不重复的。
  • 底层数据结构是哈希表，具有良好的存储和查找性能。
  • HashSet集合没有索引，只能通过迭代器或增强for循环遍历集合。

底层储存原理分析

【注】：由于HashSet的底层实现是HashMap，所以详细原理分析在HashMap模块

HashSet底层数据结构的实现是HashMap

public HashSet() {
        map = new HashMap<>();
    }
1
2
3

是一个默认长度为16，扩容因子为0.75的哈希数组。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
1
2

由于HashMap底层采用的是哈希表来进行存储数据，而哈希表是通过对象的hashCode方法计算哈希值来确定在哈希表（数组）中存储的位置（下标）。

//二次哈希计算出索引（下标），目的是为了综合高位数据，使数据在表中分布更均匀
static final int hash(Object key) {
        int h;
    	//异或运算在这相当于模上数组长度，属于优化计算效率
    	//小贴士：任何数%一个数，余数都会在0~这个数-1的范围（n%6->0~5）
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
1
2
3
4
5
6
7

插入元素时，调用HashMap的put方法，传入key和一个常量Object对象，当key重复时会丢弃准备添加的。

//可以将HashSet看作为HashMap的阉割版，因为添加数据的时候，实际put进map集合的只有key，value是一个final修饰的常量Object对象PRESENT
private static final Object PRESENT = new Object();
//添加
--------------------
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
1
2
3
4
5
6
7

扩容

当哈希数组的链表个数达到扩容因子时，即16*0.75=12时，扩容为原来的两倍

# LinkedHashSet

LinkedHashSet继承了HashSet，底层在哈希表的基础上，又维护了一条双向链表。
LinkedHashSet通过双向链表实现了元素的存取有序性。

# TreeSet

特点

  • TreeSet是Set接口下的集合。
  • 元素无索引，不重复。
  • TreeSet集合会自动对元素进行排序。
  • TreeSet底层数据结构是红黑树

排序规则

  • 元素为数字时，默认按照升序排序。（从小到大）
  • 元素为字符串时，按照字符的编码值升序排序，首字母相同比较第二个，以此类推。
  • 如果元素为自定义类型，需要制定排序规则，实现Comparable接口，重写compareTo方法。

compareTo重写示例

@Override
    public int compareTo(Student o) {
        return this.age - o.age;	//根据年龄升序排序
    }
1
2
3
4

compareTo排序规则

  • 每一次存入元素都会从根节点开始拿存入元素与当前节点比较
  • 如果返回值为负数，认为当前存入的元素是较小值，存左边。
  • 如果返回值为正数，认为当前存入的元素是较大值，存右边。
  • 如果返回值为0，认为两个元素一样，不存入集合。

若传入的泛型无法修改，可以通过传入比较器规定集合排序规则，示例：

Set<Student> list = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.getAge() - o2.getAge();	//根据年龄升序排序
            }
        });
1
2
3
4
5
6

关于double转int的精度缺失问题

Set<Double> list = new TreeSet<>(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                // return (int) (o1 - o2); 3.3 - 3.2 = 0.1  
                // 转int就是 0 这时就不会存入，出现数据丢失
                double result = o1 - o2;
                if (result > 0) {
                    return 1;
                } else if (result < 0) {
                    return -1;
                } else return 0;
            }
        });
1
2
3
4
5
6
7
8
9
10
11
12
13

# Map集合

集合结构
image.png

特点：

  • Map是一种键值对集合，每一个元素都包含一个 键对象(key) 和一个 值对象(value)。
  • Map集合中，键不允许重复，值可以重复。（比如身份证与姓名）
  • 键和值是一一对应的，通过键可以找到与之对应的唯一的值。

# HashMap

特点：

  • 以键值对的形式存储数据
  • 存储的元素是无序不重复的。
  • 底层数据结构是哈希表，具有良好的存储和查找性能。

常用方法

方法名 说明
V   put(K key,V   value) 添加元素
V get(Object   key) 根据指定的键，在Map集合中获取对应的值
V   remove(Object key) 根据键删除键值对元素
void   clear() 移除所有的键值对元素
boolean containsKey(Object key) 判断集合是否包含指定的键
boolean containsValue(Object value) 判断集合是否包含指定的值
boolean isEmpty() 判断集合是否为空
int size() 集合的长度，也就是集合中键值对的个数

Map的遍历方式1:键找值方式

通过元素中的键，获取键所对应的值

分析步骤：

  1. 获取Map中所有的键，方法提示: keySet()
  2. 遍历键的Set集合，得到每一个键
  3. 根据键，获取键所对应的值。方法提示: get(K key) | 方法名 | 说明 | | --- | --- | | Set   keySet() | 获取所有键的集合 | | V   get(Object key) | 根据键获取值 |

Map遍历方式2：键值对方式

Map中将每个键和值封装成一个个的Entry<K, V>对象，并提供 getKey() 和 getValue() 方法，用于获取Entry中封装的键和值。

  1. 获取map集合中所有 Entry<K,V> 对象的集合： entrySet()方法。
  2. 遍历Entry的集合，获取每个Entry<K,V>对象。
  3. 使用 Entry<K,V> 提供的方法获取键和值：getKey()    getValue()
方法名 说明
Set<Map.Entry<K,V>>  entrySet() 获取所有Entry<K,V>对象的集合
K  getKey() 获得键
V  getValue() 获得值

底层储存原理分析

底层数据结构是哈希表，一个默认长度为16，扩容因子为0.75的哈希数组。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Node<K,V>[] table;
1
2
3

由于HashMap底层采用的是哈希表来进行存储数据，而哈希表是通过对象的hashCode方法计算哈希值来确定在哈希数组中存储的位置（下标）。

//二次哈希计算出索引（下标），目的是为了综合高位数据，使数据在表中分布更均匀
static final int hash(Object key) {
        int h;
    	//异或运算在这相当于模上数组长度，属于优化计算效率
    	//小贴士：任何数%一个数，余数都会在0~这个数-1的范围（n%6->0~5）
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
1
2
3
4
5
6
7

插入元素时，会根据对象哈希值（调用hashCode方法）确定其在哈希表（数组）中的位置，如果该位置为空，则可将元素直接插入。如果该位置已经存在元素，则需要将该元素的key与链表中的所有元素的key逐一比较（调用equals方法），看看是否已经存在，如果不存在，则将其添加到该链中，如果存在将覆盖key对应的value。

public V put(K key, V value) {
    	//索引是通过key来计算的
        return putVal(hash(key), key, value, false, true);
    }
---------------------
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)
            //初始化长度，默认为16
            n = (tab = resize()).length;
    	//如果当前哈希数组下标没有节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            //添加新节点
            tab[i] = newNode(hash, key, value, null);
        else {
            //否则进入去重环节，因为HashMap的key是唯一的
            Node<K,V> e; K k;
            //先判断hash值是否相等，然后判断key的内容是否相同，相同则视为重复元素
            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 {//否则在链表尾部创建新节点，JDK8是尾插法，JDK7是头插法
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        
                        ....
                            
                        ++modCount;
                        // 当长度大于扩容阈值，扩容
                        if (++size > threshold)
                            resize();
                        afterNodeInsertion(evict);
                        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

扩容底层原理分析

当哈希数组的链表个数达到扩容因子时，即16*0.75=12时，扩容为原来的两倍

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) {// 旧数组容量不为0
            
            // 如果当前哈希桶容量超过最大值2^30，直接返回旧哈希桶大小
            // 因为已经到达了容量上限，再怎么hash冲突也没办法了，只能无限增加红黑树节点
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 按照两倍扩容后，如果容量没有达到上限，并且旧容量已经超过16
			// newCap翻倍，则按照两倍的方式扩容 12 -> 24 依旧是32的0.75
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 下一次扩容时参考，达到该阈值则扩容
                newThr = oldThr << 1; // double threshold（临界值翻倍）
        } 	
    	//旧数组容量等于0，进行初始化
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 将新容量设置为默认值16
			// 将扩容阈值设置为0.75*16
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    	
    	// 如果新阈值为0，按照新容量的大小重新计算下一次扩容时的阈值
		// 计算方式：采用新容量 * 负载因子
		// 即扩容的时机为：当元素个数超过阈值时则扩容if (++size > threshold)
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            // 如果新容量和阈值都是在2^30以内，下一次扩容的阈值则为ft
			// 否则改为最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
    	// 更新下一次扩容阈值
   	 	threshold = newThr;
    // 申请更多的桶，将旧哈希桶中节点转移到新哈希桶中
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            ....
        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# LinkedHashMap

LinkedHashMap继承了HashMap，底层在哈希表的基础上，又维护了一个双向链表。

LinkedHashMap通过双向链表实现了元素的存取有序性。

# TreeMap

特点：

  • nTreeMap是Map里面的一个实现类。
  • nTreeMap底层是红黑树结构；可以对元素的键进行排序。（TreeSet底层就是使用TreeMap实现存储的）
  • n排序方式有两种：自然排序，比较器排序。

TreeMap的排序

  • **自然排序：**使用无参构造器创建TreeMap集合，存入集合的键需要实现Comparable接口。
  • **比较器排序：**使用带参构造器创建TreeMap集合，传入Comparator接口的实现类。

# Hashtable与ConcurrentHashMap

  1. Hashtable 与 CoucurrentHashMap 都是线程安全的Map集合
  2. Hashtable 并发度低，整个 Hashtable 对应一把锁，同一时刻，只能有一个线程操作它
  3. 1.8之前 ConcurrentHashMap 使用了 Segment数组 + 数组 + 链表的结构，每个 Segment 对应一把锁，如果多个线程访问不同的 Segment，则不会冲突
  4. 1.8开始ConcurrentHashMap将数组的每个头结点作为锁，如果多个线程访问的头结点不同，则不会冲突

Hashtable的结构是数组+链表
image.png
1.7ConcurrentHashMap的结构是Segment数组+数组+链表的结构
image.png

  • ConcurrentHashMap有三个参数（容量，扩容因子，并发度）
  • Segment数组下标计算取二次hash的高四位，小数组的下标计算取二次hash的最低位
  • Segment[0]是Segment数组下的小数组的原型，决定小数组被创建时的默认容量
  • 小数组容量计算公式（容量/并发度）扩容阈值（元素个数大于容量x扩容因子时）
  • 1.7ConcurrentHashMap属于饿汉式单例，在创建对象时就会开辟内存空间。

1.8后变成数组+链表 | 红黑树的结构
image.png

  • 1.8ConcurrentHashMap属于懒汉式单例，在调用put方法时才会开辟内存空间。
  • 1.8ConcurrentHashMap扩容时是从数组尾部开始检查的，一个节点一个节点的进行迁移，迁移完的节点会有标记，当扩容时线程进行了get方法，对于已迁移完的节点，就需要去迁移后的新数组中找，而这里就会牵扯到部分链表对象重新创建，防止地址指向出现问题；当扩容时线程调用了put方法，若是put在未迁移的位置，则可以并发执行，若是put在正在迁移的位置则会阻塞，要等待数据迁移结束，若是put已经迁移完的位置则要帮忙进行迁移，等数据全部迁移到新数组后才能put。

# Properties属性集

所属体系
image.png

概述

Properties类表示属性集。他是一个特殊的集合，可以结合IO流操作。

  • Properties实现了Map接口，就是一个双列集合可以存储键值对数据，键和值都是字符串类型。
  • Properties可以结合流进行操作，可以把集合中的数据保存到流中，也可以从流中来加载数据。

特有方法

方法名 说明
Object setProperty(String key, String value) 添加键和值，键和值都是String类型
String getProperty(String key) 通过键获取值
Set<String> stringPropertyNames() 获取所有的键
void load(Reader reader) 从输入字符流读取属性列表（键和值）
void load(InputStream inStream) 从输入字节流读取属性列表（键和元素对）
void store(Writer writer, String comments) 将Properties中的键和值写入输出字符流中
void store(OutputStream out, String comments) 将Properties中的键和值写入输出字节流中

**补充：**properties属性集常用于操作.properties结尾的配置文件，里面的内容一行一个key=value

#java#数据结构
上次更新: 2023/12/29 11:32:56
基础篇
IO流

← IO流→

最近更新
01
JVM 底层
09-13
02
JVM 理论
09-13
03
JVM 应用
09-13
更多文章>
Theme by Vdoing | Copyright © 2022-2024 kinoko | MIT License | 粤ICP备2024165634号