数据结构

抽象数据类型
列表、栈、队列

实现数据结构
是否重复有序

不同的链表
单链表、双端链表、双端双向链表

LinkedList、ArrayList
大小固定,有下标
插入删除,效率都是O(N)
add、remove、contains、indexof

ArrayList、Vector
默认容量
10
默认最大容量
Integer最大值-8
扩展容量
ArrayList,原来+原来的一半;旧size+新size;Integer最大值
Vector,不指定增量两倍,指定增量增加增量指定的大小;……

栈、队列、优先级队列
应用
栈,算术表达式、校验括号、单词逆序、图深度优先搜索、栈操作存在于微处理器中及方法调用过程;
队列,打印队列、文字处理软件、图广度优先搜索;
优先级队列,航母、导弹、飞机、潜艇,抢先式的多任务操作系统、时间片
实现
优先级队列,有序数组(不适用环绕),

,从根到任意一个节点有且只有一条路径;类似链表,插入删除。
查找树,借鉴了有序数组的优点,二分查找。
平衡树,AVL树、红黑树、2-3树、2-3-4树
二叉树,算术表达式、哈夫曼树压缩、堆树、平衡的二叉查找树
AVL树
单旋转,带平移的旋转,双旋转;新添加的节点位于内侧时,需要双旋转
红黑树
节点有色,根黑,父红子必黑,黑色高度相同
红黑树新增
新增必红;路上父黑两子红改变颜色;新增后红红冲突
效率
大O表示法,新增删除查询O(logN)
AVL树,最差,查log2N,新增删除2log2N
红黑树,最差,查2log2N,新增删除和查询几乎相同,平均一次大约改变一次颜色旋转一次
树的缺点,和列表比遍历慢、和哈希表比增删改查慢

TreeMap,由红黑树实现
private transient Entry<K,V> root;
static final class Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

put方法
cmp = k.compareTo(t.key); // cmp是int类型的,是比较器比较的结果
if (cmp < 0)
    t = t.left;
else if (cmp > 0)
    t = t.right;
else
    return t.setValue(value); // 如果key相同,覆盖旧value并返回

TreeSet,底层是TreeMap
private static final Object PRESENT = new Object();
public TreeSet() {
    this(new TreeMap<E,Object>());
}
public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}

堆树
完全树,不是查找树;
插入,最后一个节点旁边,调整顺序;
删除,根节点,把最后一个元素复制过来,调整顺序。
数组实现
无洞,位置固定
应用
优先级队列

2-3-4树
定义:非叶节点可以有2个、3个或4个子节点。
特点:平衡树,所有叶节点都在同一层上;查找树,数据项有序。
查找:和二叉搜索树类似
插入:新的数据总是插在叶节点里,在查找插入的路径上,碰到满节点时,满节点要分裂,正是这种分裂保证了树的平衡。
转换:红黑树

2-3树
和2-3-4树相比,除了子节点数不一样外,其它的都完全一样。
插入:在查找插入位置的过程中不理会遇到的节点是不是满的,顺着树找到要插入的叶节点,如果叶节点不满,就插入新值; 如果叶节点满了,分裂叶节点,新的数据必须参与分裂过程。

读写硬盘
1、移动磁头到正确的磁道
2、旋转磁盘
3、读写头的读写时间和块容量关系不大,块越大效率越高

B树,插入类似2-3树

B+树
1、只有叶节点保存数据,非叶节点只保存关键字和块号码
2、非叶节点有n个数据项,就有n个子节点;
3、叶节点有序且互相连接
索引是由关键字-块号码对组成的按关键字排序的列表或树。
多级索引,同一个文件有多个索引,每个索引的关键字不同。索引和文件比起来很小,不会大量增加数据存储量;但删除数据时,需要把所有索引的那个键-号码对都删除。
子节点指针是子节点的块号码,数据项保存关键字和该块块号码。
查询快
插入快
1、把新关键字和块号码插入到索引中,有顺序
2、把数据插入主文件,不需要移动硬盘内容,加在末尾就可以(文件里的记录按照任意顺序排列,比如可以按插入时间排序)

MySQL
MyISAM引擎的索引是非聚集索引,叶子节点保存的都是数据行的地址
InnoDB引擎的主键索引是聚集索引,辅助索引是非聚集索引(叶子节点保存着主键的值)。
InnoDB的表必须有主键,业务无关的自增字段作为主键。如果没有显式指定...
 
InnoDB支持行锁和事务
联合索引之最左前缀原理

建立联合索引,也就是对多个字段建立索引,无论是oralce还是mysql都会让我们选择索引的顺序。比如,想在a,b,c三个字段上建立联合索引,可以选择,a、b、c,或者b、a、c,或者c、a、b。为什么需要顺序呢?这样就引出了数据库索引的最左前缀原理。

比如:索引 index1:(a,b,c)

select * from table where c = ‘1‘ ———— 不走索引,
select * from table where b =‘1’ and c =‘2‘ ———— 不走索引。

下列语句走索引:
select * from table where a = ‘1‘  
select * from table where a = ‘1‘ and b = ‘2’  
select * from table where a = ‘1‘ and b = ‘2’  and c=‘3‘

索引index1:(a,b,c),只会走a;a,b;a,b,c 的查询。
a,c也走,但是只走a,不走c。

另外还有一个特殊情况
select * from table where a = ‘1‘ and b > ‘2’  and c=‘3‘ ————只走a与b的索引。


查看索引解释计划:
可以看到走了索引MyIndex,key_len=303,PARENT_ID字段的类型是varchar(100) NULL,所以key_len=100*3+2+1=303。说明只走了主键字段的索引。
key_len的计算方法,不同字符集计算方式不一样。


前缀索引,与选择性有关,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,使得前缀索引的选择性接近全列索引,同时减少了索引文件的大小

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作
索引可以加快查询速度,但并不是查询语句需要,就可以建立索引。
1、索引文件本身要消耗存储空间
2、索引会加重插入、删除和修改记录时的负担
3、表记录比较少,不超过两千条记录的表,没必要建索引,让查询做全表扫描就好了
4、索引的选择性较低,如性别列不适合作索引

 
哈希化
通过哈希函数把一个数字从大的范围转化为小范围的数字叫哈希化
把一部英文字典装入哈希表,A是1,B是2,C是3,依此类推,Z是26,a是27,空格是0,一共53
1、数字相加 BBC=2+2+3=7
假设单词最长有10个字母,53*10=530
2、幂的连乘
888= 8*102 + 8*101 + 6*100
BBC= 2*532 + 2*531 + 3*530
这样每个单词对应独一无二的一个数字
最长的10个字母的单词ZZZZZZZZZZ,将转化成26*539+26*538+26*537+26*536+26*535+26*534+26*533+26*532+26*531+26*530,内存中的数组根本不可能有这么多的单元,产生的数组下标太多
3、哈希函数
取余法:index = x / arrayLength

哈希化后的冲突
1、开放地址法
装填因子是二分之一或三分之二时,哈希表的性能最好,装填因子接近1时,哈希表效率非常低; 所以设计数组大小应该两倍于需要存储的数据量。
线性探测、 二次探测、再哈希法,
再哈希法和二次探测要求数组容量是一个质数,否则会造成死循环
2、链地址法
当装填因子是1时,大约三分之一的单元是空白单元,三分之一的单元有一个数据项,三分之一的单元有两个或更多的数据项。
链地址法装填因子可以达到1以上,对性能影响并不大;找到初始单元需要O(1)的时间级,搜索链表的时间与链表的平均数据项成正比。
当表容量不是质数时,还是能够导致聚集

哈希表优点
哈希表比树快,插入、查找、删除时间复杂度都接近O(1)。
缺点:
1、基于数组,难于扩展
2、无序

public Hashtable() {
    this(11, 0.75f);
}
new Hashtable时我们输入的容量是多少就会创建多大的数组
扩展容量,2倍+1,int newCapacity = (oldCapacity << 1) + 1;
Hashtable的哈希方法用到了取模运算
如果hash和key都相同,覆盖value的值
if ((entry.hash == hash) && entry.key.equals(key)) {
    V old = entry.value;
    entry.value = value;
    return old;
}

HashMap
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
默认容量16,1 << 4; 最大容量,1 << 30; 负载因子,不指定默认0.75f;
初始容量,由tableSizeFor()方法确定,该方法返回值总是2的幂,传入7,返回8;传入13,返回16。
计算下标,i = (n - 1) & hash,i是下标,n是数组容量,hash是hash值

扩容
if (oldCap >= MAXIMUM_CAPACITY) {
    原数组长度大于最大容量(1073741824) 则将threshold设为Integer最大值2147483647
    threshold = Integer.MAX_VALUE;
    return oldTab;
}
    数组容量扩展至原来的两倍,阈值也扩展至原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

// 冲突了    
else {
// 相同的key,先比较hash,再比较key
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;        
    // 如果链表元素大于等于8个,把数据放入一个红黑树
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    // 红黑树
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}    

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        // 如果是key相同,会把新的value覆盖旧的value
        e.value = value;
    afterNodeAccess(e);
    // 并返回旧的value
    return oldValue;
}    

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 比较hash,且比较key,如果相同,就返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 判断是不是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}            

按位与都为1结果为1;按位或有一个是1结果就是1;异或,不同为1,相同为0

HashSet由哈希表实现
// 无参构造方法
public HashSet() {
map = new HashMap<>();
}
// 有参构造方法
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 有参构造方法,创建的是一个LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
// /?preznt/ 现在的
private static final Object PRESENT = new Object();
 
public boolean add(E e) {
/* 如果e是重复的,也就是key相同,
* HashMap会用新的value覆盖旧的value,
* 但在这里其实两个value是一样的,都是PRESENT
* 接着返回旧的value,不等于null,最后返回false
*/
return map.put(e, PRESENT)==null;
}
 
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}

LinkedHashMap既是一个HashMap,也是一个双端双向链表
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
 
// HashMap.Node
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Collections 是一个操作 Set、List 和 Map 等集合的工具类。
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
Collections类中的方法有:
sort()、binarySearch()、reverse() —— 反转、shuffle() —— 乱序
min()、max()、copy()、swap(List,int, int)
int frequency(Collection,Object):返回指定集合中指定元素的出现次数
boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值

List的实现类:ArrayList、LinkedList、Vector,Stack是Vector的一个子类。
Dictionary被Map取代,Hashtable实现了Dictionary,Properties是Hashtable的一个子类;Properties的key和value都是字符串类型。
Properties properties = System.getProperties();

数组,新增快,查询慢O(N),插入删除慢O(N)
链表,新增快,查询慢O(N),插入删除快O(N)
树,log2N
哈希表,O(1)

顶点、边
顶点可以使用列表保存、顶点间的关系可以使用邻接矩阵或邻接表保存
深度优先搜索、广度优先搜索
有向图、加权图
北京——>齐齐哈尔,有向加权图,有几条路、有没有直达车、最短时间的线路
 

相关推荐