java集合-双列集合

base-exajava: https://gitee.com/designMode_apple/base-exajava.git

JDK 17 Documentation - Home

HashMap (Java SE 17 & JDK 17)

map

Map是不是Entry的容器  Entry<K,V>是一个key-value集合

线程不安全，适合在单线程中使用

结构

数组+链表+二叉树，红黑树1.8

1.   数组  查询快
2.   链表  插入快
3.   红黑树   数据多时，查询快

 每次遍历一个链表，平均查找的时间复杂度是 O(n)，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。

        那为什么不一开始就用红黑树，反而要经历一个转换的过程呢？其实在 JDK 的源码注释中已经对这个问题作了解释： Because TreeNodes are about twice the size of regular nodes, use them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due removal or resizing) they are converted back to plain bins.

      这段话的意思是：单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间。 通过查看源码可以发现，默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，这体现了时间和空间平衡的思想，最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树，需要确定一个阈值，这个阈值默认为 8，并且在源码中也对选择 8 这个数字做了说明，原文如下： In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:

0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million

       上面这段话的意思是，如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。 但是，HashMap 决定某一个元素落到哪一个桶里，是和这个对象的 hashCode 有关的，JDK 并不能阻止我们用户实现自己的哈希算法，如果我们故意把哈希算法变得不均匀，例如： @Override public int hashCode() { return 1; }

这里 hashCode 计算出来的值始终为 1，那么就很容易导致 HashMap 里的链表变得很长。让我们来看下面这段代码：

public static void main(String[] args) {
    HashMap map = new HashMap<HashMapDemo,Integer>(1);
    for (int i = 0; i < 1000; i++) {
        HashMapDemo hashMapDemo1 = new HashMapDemo();
        map.put(hashMapDemo1, null);
    }
    System.out.println("运行结束");
}
 
@Override
public int hashCode() {
    return 1;
}

   在这个例子中，我们建了一个 HashMap，并且不停地往里放入值，所放入的 key 的对象，它的 hashCode 是被重写过得，并且始终返回 1。这段代码运行时，如果通过 debug 让程序暂停在 System.out.println("运行结束") 这行语句，我们观察 map 内的节点，可以发现已经变成了 TreeNode，而不是通常的 Node，这说明内部已经转为了红黑树。

事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。 通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。 所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突。

存储

  把key对象通过hash()方法计算hash值，然后用这个hash值对数组长度取余数（默认16），来决定该对KEY对象存在哪里。默认加载因子为0.75，默认数组大小是16

扩容

扩容 一定程度上也防止了hash 碰撞

  扩充次数过多，会影响性能，每次扩充表示哈希表重新散列（重新计算每个对象的存储位置） 我们在开发中尽量要减少扩充次数带来的性能问题。 存值尽量分散

api

V get(0bject key)

  获取与键关联的值;返回与键关联的对象，

  如果映射中没有这个对象，则返回null。实现类可以禁止键为 null

V put(K key, V value)

  如果这个键已经存在，新的对象将取代与这个键关联的旧对象。这个方法将返回键关联的旧值

 如果之前没有这个键，则返回 null。实现类可以禁止键或值为 null。

void putAll(Map<? extends K,? extends V> entries)

  将给定映射中的所有映射条目添加到这个映射中。

  相同的key值则返回原集合中的value ,不同的key则添加进去 返回为空

boolean containsKey(0bject key)

  如果在映射中已经有这个键，返回 true。

boolean containsValue(0bject value)

  如果映射中已经有这个值，返回 true。

void clear()

boolean isEmpty()

Set<K> keySet()

Collection<V> values()

V remove(Object key)

新API

default V getOrDefault(0bject key, V defaultValue) 8

putIfAbsent(K,V) 只会添加不存在相同key的值 避免覆盖

初始化大小

expectedSize/0.75+1

GUAVA   Maps.newHashMapWithExpectedSize()

LinkedHashMap

双重链表来维护如果要保证map中存放的key和取出的顺序一致

C->B->A

新增D:D->C->B

新增C:C->D->B

        LRUCache<T> 

TreeMap

Hashtable

Hashtable 线程安全集合，运行速度慢

Hashtable 命运和Vector是一样的,从JDK1.2开始,被更先进的HashMap取代

HashMap 允许存储null值,null键

Hashtable 不允许存储null值,null键

基于哈希表实现（数组+链表)默认数组大小为11，加载因子0.75

扩充方式：原数组大小<<1 (*2) +1

Properties

Properties()

创建一个空属性映射

Properties(Properties defaults)

用一组默认值创建一个空属性映射

String getProperty(String key)

获得一个属性。返回与键（key）关联的值，或者如果这个键未在表中出现，则返回默认值表中与这个键 关联的值，或者如果键在默认值表中也未出现，则返回 null

String getProperty(String key,String defaultValue)

如果键未找到，获得有默认值的属性。返回与键关联的字符串，或者如果键在表中未出现，则返回默认字 符串。

0bject setProperty(String key,String value)

设置一个属性。返回给定键之前设置的值。

void load(InputStream in) throws IOException

从一个输入流加载一个属性映射。

void store(0utputStream out,String header)1.2

将一个属性映射保存到一个输出流。header 是所存储文件的第一行。

java.tang.System 1.0

Properties getProperties()

获取所有系统属性。应用必须有权限获取所有属性，否则会抛出一个安全异常。

String getProperty(String key)

获取给定键名对应的系统属性。应用必须有权限获取这个属性，否则会抛出一个安全异常。以下属性总是 允许获取

 枚举和映射

EnumSet 是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet 内部用位序列实现。如果对应的值在集中，则相应的位被置为。

EnumSet类没有公共的构造器。要使用静态工厂方法构造这个集∶

enumWeekday{ MONDAY,TUESDAY,WEDNESDAY,THURSDAY,FRIDAY,SATURDAY,SUNDAY };
EnumSet<Weekday> always = EnumSet.all0f(Weekday.class);
EnumSet<Weekday> never = EnumSet.none0f(Weekday.class);
EnumSet<leekday> workday = EnumSet.range(Weekday.MONDAY, weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY,Weekday.WEDNESDAY,Weekday.FRIDAY);

可以使用 Set 接口的常用方法来修改 EnumSet。

EnumMap 是一个键类型为枚举类型的映射。它可以直接且高效地实现为一个值数组。需要在构造器中指定键类型

var personInCharge = new EnumMap<Weekday,Employee>(Weekday.class)

static <E extends Enum<E>> EnumSet<E> all0f(Class<E> enumType)

返回一个包含给定枚举类型的所有值的可变集

static <E extends Enum<E>>Enunset<E> none0f(Class<E> enumType)

返回一个初始为空的可变集

static <E extends Enum<E>> EnumSet<E> range(E from, E to)

返回一个包含 from～to之间的所有值（包括两个边界元素）的可变集

static <E extends Enum<E>> EnumSet<E> of(E e)

static <E extends Enum<E>> EnumSet<E> of(E el, E e2,E e3,E e4,E e5)

static <E extends Enum<E>> EnumSet<E> of(E first,E... rest)

返回包括不为 null 的给定元素的可变集。

java,util.EnumNap<( extends Enum<K>,V> 5

EnumMap(Class<K> keyType)

构造一个键为给定类型的空的可变映射。

 标识散列映射

类 IdentityHashMap有特殊的用途。在这个类中，键的散列值不是用 hashCode 函数计算的，而是用 System.identityHashCode 方法计算的。这是 Object.hashCode 根据对象的内存地址计算散列码时所使用的方法。而且，在对两个对象进行比较时，IdentityHashmap类使用=而不使用equals。

也就是说，不同的键对象即使内容相同，也被视为不同的对象。在实现对象遍历算法（如对象串行化）时，这个类非常有用，可以用来跟踪哪些对象已经遍历过。