栈和队列的特点：
栈的模型是底端闭口的 顶端开口 增删查等操作都是要从顶端开始（先进后出）。
栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其 他任何位置进行添加、查找、删除等操作。
队列的模型是列车 左进右出 就好比排队 右边的先走 晚来的就排在后面更上（左进右出）
队列：队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入， 而在表的另一端进行删除。
2.数组和链表特点
链表是多个结点之间，通过地址进行连接。例如多个人手拉着手：查找慢 增删快
链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每 个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。我们常说的 链表结构有单向链表与双向链表。
数组查询快增删慢。(规定好的空间，多了）
数组：Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排 出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。
面试题：二叉树 和红黑树
二叉树：(binary tree)是每个结点不超过2的有序树（tree） 。
简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都多只能有两个子结点。
二叉树是每个节点多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。
红黑树五大约束
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
扩展了解：在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，可以用可变参数的方法实现：
public class Test1 {
public static void main(String[] args) {
int[] arr = {1, 4, 62, 431, 2};
int sum = getSum(arr);
System.out.println(sum);
int sum2 = getSum(6, 7, 2, 12, 2121);
System.out.println(sum2);
}
private static int getSum(int... arr) {
int sum = 0;
for (int a : arr) {
sum += a;
}
return sum;
}
}
在HashMap链表项大于8时自动转换成红黑树
整个方法的大体的执行是第一次循环会将链表中的第一个节点作为红黑树的根，后面的循环会通过比较链表中的项的hash值，放到树节点的左边或者右边，因为添加操作可能会破坏树的结构，所以最后会做一次balanceInsertion
这个方法里面将会进行旋转和颜色变换，具体的原理就是依据红黑树的规则
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY = 64,这里是重点，如果table小于64，那么是走的扩容resize的方法，超过这个数字，才会走到else的TreeNode的构建
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//自动扩容，后续专门一篇文章介绍这个
resize();
// 通过hash求出bucket的位置。
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
// 将每个节点包装成TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
// 将所有TreeNode连接在一起此时只是链表结构
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
这个方法的操作是将目前的9个项通过链表的方式链接在一起，以他为基础，构建红黑树
看下TreeNode类的源码，发现对红黑树的操作都是在TreeNode内部
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//遍历传入的链表
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//为根结点赋值
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
//x是当前访问链表中的项
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//此时红黑树已经有了根节点，上面获取了当前加入红黑树的项的key和hash值进入核心循环，从root开始是一个自顶向下的方式遍历添加
//for循环没有控制条件，由代码内部break跳出循环
for (TreeNode<K,V> p = root;;) {
//dir：directory，ph：parent hash
int dir, ph;
K pk = p.key;
//比较当前项与当前树中访问节点hash值判断加入项的路径，-1为左子树，+1为右子树
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//xp：x parent，找到符合x添加条件的节点
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
//如果xp的hash值大于x的hash值，将x添加在xp的左边，否则，添加在xp的右边
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//添加节点后，维护添加后红黑树的红黑结构
root = balanceInsertion(root, x);
//跳出循环，代表当前链表中的项成功的添加到了红黑树中
break;
}
}
}
}
moveRootToFront(tab, root);
}
网友评论