数据结构
本文准备讲一下软件开发中的数据结构。
物理存储
因为数据结构是用来存储数据的具体方式，在讲数据结构之前，说说数据物理存储。
平时软件开发中，一个8G的内存可以同一时间存储8G的数据，在物理上来说，这些存储单元是连续的，理论上可以可以看成是地址从0开始到 8*2^30次方。理想的话，什么数据通过寻址就能找到，很方便
但是数据的使用在计算机中并不只是查询，也可以是修改，添加，删除，移动，考虑的数据安全，运算速度，使用效率的等综合，基于物理硬件的软件数据结构往往并不只有数组，还有其他，比如链表，图，树等。
在复杂的情况下，各种各样的运算，不同程序的进程，线程都在使用这些内存或者cpu资源，这些数据通过软件的角度去解读，肯定存在差异的结构，在物理上底层都是数组。
数组
数组，是数据最基本的存储结构，数组表示同一种数据有多个。
数组的优点是查询快，通过索引能够快速找到。
但是数组优缺点，就是修改数组长度的时候，很麻烦。
示意
数组 内容为
1
char[] arrays = {'a','p','p','l','e',' ',' ','1','3','6','6','8','5','$'}
要修改数组，将arrays[5] = ‘5’ arrays[6] = ‘$’;,然后删除arrays[6]之后的数据，
最终 arrays变为 arrays = {'a','p','p','l','e','5','$'}
大致过程如下，
使用数组的时候，当你查看数据时，特别方便快色，如你要查看数组的第2个元素 直接arrays[1]就能访问获得元素内容’p’
但是删除元素的时候却很麻烦，如上图删除index = 5~12的元素，之后你还需要将 index = 13 ~14 的内容搬到 index = 5~6 上面，并且将index等于 7~14的存储单元清空还给计算机管理（空间高效利用原则）
这还不是最坏的情况，数组是连续的，如果有一个10000位的数组，你只是删除了第一个元素，那么后面9999个元素都要向前移动一位，这明显不是很好的数据使用方式，或者多种数据结构在不同使用场景下使用。
链表
链表是一种带有下一个元素信息的数据结构，链表有开头和结尾，并且链表不需要一定是连续的存储单元
链表针对数组元素的添加和删除，有了明显直观的优化，链表是不连续的存储单元存储数据，每个存储单元都存有内容+next缩影，通过next索引找到下一个数据
因此删除数据的时候，只需删除一个数据，要将next索引修改一下就好了，不会像数组那样大规模修改数据。
上面删除apple 链表的 ‘i’元,将链表第三个单元‘p’的next 地址修改位指向 e，再删除‘i’即可
链表删除增加很快，但是如果有长度1000的链表，查看第500个元素，只能从第一个开始，通过next寻址500此才能找到元素。
树
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。
度 树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 深度 树的深度——组成该树各结点的最大层次，如上图，其深度为4； 层次 根结点的层次为1，其他结点的层次等于它的父结点的层次数加1. 路径 对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1. 森林 指若干棵互不相交的树的集合
树与数组的区别
查询一个数据是否存在，
数组是全部展示，没有深度，你有索引的情况下能快速查找，如果没有索引，需要一个个查看内容对比。
树有层次，有深度和宽度，也有索引，索引与元素内容有关联，如二分查找法，可以快速得知数据是否存在，而不是每个数据依次查看。
个人理解树是有层次的数据结构，有深度和宽度，在某些查询场景上比数组数据结构更加高效快速
文件系统可以看作树结构的经典应用。
HashMap
可以看出数组和链表是两种区别很大的数据结构，数组查询快，增删慢，链表相反，查询慢，增删快
如果能将这两个数据结构的有点结合，就能很好的去操作数据了，提升性能和数据处理速度，Java中的HashMap就是一个将数组和链表有点结合的数据结构，接下来探索了解Java中的HashMap数据结构
存值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
哈希值
hash值计算是一种获取不重复值的算法，通常key不同，返回的数值不同
1
2
3
4
5
6
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public native int hashCode(); //jvm本地方法
索引算法
1
2
3
4
5
6
putVal(hash(key), key, value, false, true);
// 实际存值代码
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// i = (n - 1) & hash i就是计算出的索引值
快速查找
HashMap类似数组的快速定位查找与哈希计算和数组有关
下面是HashMap构造和查询有关的代码
1
2
3
4
5
6
7
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
table 是一个数组，数组元素的结构是Node
1
2
3
4
5
6
7
8
9
10
11
12
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //指向像一个元素，是一种链表结构的应用
//... 省略一些代码
}
Node 是类似链表结构，成员属性包含一个Node<K,V> next 有next是防止hash碰撞等情况
get方法获取值（查找）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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) {
//判断如果table不是空 取值 tab[(n - 1) & hash]
//可以看出数组索引是 (n-1) & hash 这里其实是位运算得出数组索引
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first; //判断key完全相同则返回内容
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;
}
索引冲突
关于HashMap中 table数组索引的确定(根据key)
1
2
3
hash = hash(key); //通过key获取hash值
n = tab.length; //获取数组长度 值一定是2的n次方(可以看HashMap中resize方法了解细节)
index = (n - 1) & hash //在存值和取值的时候，算出index，数组的索引
table.length 是一个 2的n次方值，也就是说 n-1 一定是 0000011111这种类似结构
n = 8； 二进制 1000
n - 1 = 7 二进制 0111
如果一个key的hash值为十进制数86，二进制为1010110， 那么 n=8时
(n-1) & 1010110 = 0000111 & 1010110 它的结果是 0110 换算十进制为 6，直接找到元素位置table[6];
hashmap在实际使用时可能有key不同，索引值相同的情况。
当两个key虽然hash值不同，table.length = 8的时候，两个key的hash值不同，一个值是keyHash1=23001，一个值是keyHash2=20001，这两个值在(n-1) & hash的位运算中，结果都是1，所以index = 1，这时候需要用到链表去解决这种问题，
table[1] = node1;
node1.key = key1,node1.value = value1 node1.next = node2
node2.key = key2,node2.value = value2 node2.next = null;
链表改为树结构
如果node过多，后面会将链表改为树结构
1
2
3
4
5
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 链表改为树的逻辑判断
treeifyBin(tab, hash);
// TREEIFY_THRESHOLD的定义
static final int TREEIFY_THRESHOLD = 8;
可以知道当链表元素超过7个，为了查询效率，会把当前链表结构改为树结构