一、HashMap用到的数据结构

哈希表、数组、链表、红黑树

数组、链表这里不再讲了

1.哈希表

(1).哈希表定义:

哈希表又叫散列表，是一种根据设定的映射函数f(key)将一组关键字映射到一个有限且连续的地址区间上，并以关键字在地址区间中的“像”作为元素在表中的存储位置的一种数据结构。这个映射过程称为哈希造表或者散列，这个映射函数f(key)即为哈希函数也叫散列函数，通过哈希函数得到的存储位置称为哈希地址或散列地址

(2).哈希冲突定义:

对于不同的关键字，可能得到同一个哈希地址，即key1≠key2,而 f(key1)=f(key2)，对于这种现象我们称之为哈希冲突，也叫哈希碰撞

(3).处理哈希冲突:

一个好的哈希算法有助于减少哈希冲突。

举两个例子例如：

1).除留取余法

这个方法我们在上边已经有接触过了。取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址。即：f(key)=key % p, p≤m;

2).直接定址法

直接定址法是指取关键字或关键字的某个线性函数值为哈希地址。即： f(key)=key 或者 f(key)=a*key+b

(4).如何处理哈希冲突

举两个例子例如:

1).链地址法

链地址法是指在碰到哈希冲突的时候，将冲突的元素以链表的形式进行存储。也就是凡是哈希地址为i的元素都插入到同一个链表中，元素插入的位置可以是表头（头插法），也可以是表尾（尾插法）

2).再哈希法

再哈希法即选取若干个不同的哈希函数，在产生哈希冲突的时候计算另一个哈希函数，直到不再发生冲突为止。

2.红黑树

二叉树详解_Allence的博客-CSDN博客1.这里就不介绍二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念2.二叉树的分类(1).斜树斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。左斜树:右斜树:(2).满二叉树国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树。如下图所示：注意：这里的定义与国内某些教材的定义不同，国内的定义是：https://blog.csdn.net/m0_37707561/article/details/122866425

二、源码分析

 1.重要的属性

(1).默认的长度

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

(2).最大长度

    static final int MAXIMUM_CAPACITY = 1 << 30;

(3).平衡因子

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

(4).树化条件

    static final int MIN_TREEIFY_CAPACITY = 64;
    static final int TREEIFY_THRESHOLD = 8;

只有在长度大于64并且链表长度大于8、大于等于9时才会树化，如果散列表（数组）长度小于64而链表的长度大于8，这时会触发扩容不会树化。