查找

为什么要用equals()?为什么不一直用从compareTo()?
因为并不是所有的对象都实现了Comparable接口，但所有的对象都继承了Object类，所以都可以equals()

二叉查找树 BST (Binary Search Tree)

又称二叉排序树
二叉查找树 不是 平衡的二叉树

平衡查找树 ALV (balanced binary tree)

又称平衡二叉树。

1. 左子树和右子树的高度之差的绝对值不超过1
2. 左子树和右子树也是平衡的

红黑树

红黑树是二叉查找树，是黑色平衡的，不是平衡的。存在红节点和黑节点。
红节点 表示该节点 与 该节点的父链接 是红色的。
黑节点 表示该节点 与 该节点的父链接 是黑色的。
红黑树有如下特点：

1. 红链接全为左链接。
2. 没有任何一个结点同时和两条红链接相连。两个红链不相连。
3. 如果一个节点是红的，那它的两个子节点都是黑的。
4. 红黑树是完美黑色平衡的，即任意叶节点到根结点的路径上的黑链接数量相同。
5. 对每个节点，从该节点到其子孙叶节点的所有路径上，包含相同数目的黑节点。
6. 红黑树不一定是平衡二叉树，如果红色不算链的话，它是完美平衡二叉树。
7. 叶节点不可能出现一黑的情况，但可能出现一红的情况。
8. 黑叶节点必须存在黑节点兄弟，不能存在红节点兄弟，否则不满足黑色完美平衡。
9. 红叶节点不会存在兄弟，如果存在红兄弟，那么不满足两个红链不相连；如果存在黑兄弟，那么不满足黑色完美平衡。
10. 根节点是黑的，但它的左节点可能是红的。

B树

B树，是平衡多路查找树，m阶B树又叫平衡m叉查找树。一棵m阶的B树的特点如下：（m阶= =度为m= =个m叉）

1. 根节点有 [2, m] 个孩子（除非B树只包含一个节点）
2. 除根节点，其他每个分支节点有$[\lceil m/2 \rceil, m]$个孩子
3. 根节点有 [1, m-1] 个关键字（除非B树只包含一个节点）
4. 除根节点，其他每个分支节点有$[\lceil m/2 \rceil-1, m-1]$个关键字
5. 所有点节点都出现在同一层上，叶节点不包含任何关键字信息
6. 有j个孩子的非叶节点恰好有j-1个关键字，关键字按递增顺序排列

Best case (最低高度) and worst case (最高高度) heights

Let h be the height of the classic B-tree. Let n > 0 be the number of entries in the tree. Let m be the maximum number of children a node can have. Each node can have at most m−1 keys.
It can be shown that a B-tree of height h with all its nodes completely filled has $n=m^{h+1}-1$ entries. Hence, the best case height of a B-tree (where the root node is considered to have height 0) is:
$$\lceil log_m(n+1)\rceil$$
Let d be the minimum number of children an internal (non-root) node can have. For an ordinary B-tree, d=⌈m/2⌉. Comer (1979, p. 127) and Cormen et al. (2001, pp. 383–384) give the worst case height of a B-tree (where the root node is considered to have height 0) as:
$$h\leqslant \lfloor log_d(\frac{n+1}{2})\rfloor$$ 根节点二叉，非根节点d叉，d=⌈m/2⌉
$n\geqslant 1+2(d^h-1)$
$n\geqslant 2d^h-1$
$\frac{n+1}{2}\geqslant d^h$
$log_d\frac{n+1}{2}\geqslant h$

散列表

每种数据类型的hashCode()方法都必须和equals()一致。

1. 如果a.equals(b)返回true，那么a.hashCode()==b.hashCode()
2. 如果a.hashCode()==b.hashCode()，那么a.equals(b)不一定返回true，还需用a.equals(b)比较
3. 如果a.equals(b)返回false，那么a.hashCode()!=b.hashCode()
4. 如果a.hashCode()!=b.hashCode()，那么a.equals(b)一定返回false

构造hashCode()

Integer的hashCode是int

1
2
3
4
5
6

public int hashCode() {
    return Integer.hashCode(value);
}
public static int hashCode(int value) {
    return value;
}

Double的hashCode也是int

1
2
3
4
5
6
7

public int hashCode() {
    return Double.hashCode(value);
}
public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

String的hashCode()是每个char的计算结果，也是int

1
2
3
4
5
6
7
8
9
10
11
12

private int hash; // Default to 0
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

如果你要为自定义的数据类型定义散列函数，则需要同时重写hashCode()和equals()。默认散列函数会返回对象的内存地址。Java中很多数据类型都重写了hashCode()方法，包括String，Integer，Double，File和URL。

重写：子类的方法覆盖父类的方法，要求方法名和参数都相同
重载：在同一个类中的两个或两个以上的方法，拥有相同的方法名，但是参数却不相同，方法体也不相同，最常见的重载的例子就是类的构造函数。

Reference

https://en.wikipedia.org/wiki/B-tree

• ← Previous Post
• Next Post →