Java数据结构-（一）

发表于 | 评论数： | 阅读次数：

1.接口 Collection Set Map List Queue Stack
2.常用哪些 排序 常用方法
3.实现原理 各个Jdk版本优化
4.存储结构 链表 数组 初始化容量 扩容机制 优点
5.线程安全 线程安全实现方式

继承关系

Java数据结构继承关系

注意List和Set继承Collection Map没有继承Collection

List

1.ArrayList
2.LinkedList
3.CopyOnWriteArrayList

ArrayList

1.内部通过数据实现

1
transient Object[] array;

2.扩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static final int MIN_CAPACITY_INCREMENT = 12;

@Override public boolean add(E object) {
    Object[] a = array;
    int s = size;
    if (s == a.length) {
        //当前容量 小于6个 增加12个位置 大于6个 增加一倍
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

3.线程不安全 多线程会出现ConcurrentModificationException异常

LinkedList

1.内部通过链表来实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
transient Link<E> voidLink;

private static final class Link<ET> {
    ET data;

    Link<ET> previous, next;

    Link(ET o, Link<ET> p, Link<ET> n) {
        data = o;
        previous = p;
        next = n;
    }
}

2.扩容机制 不存在扩容问题 

1
2
3
4
5
6
7
8
9
private boolean addLastImpl(E object) {
    Link<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

3.同样线程不安全 多线程会出现ConcurrentModificationException异常
4.比较ArrayList LinkedList
ArrayList 在中间插入数据比较负责 需要做拷贝工作 寻找数据比较简单 数组下标
LinkedList在任意位置插入数据比较简单 链表操作 查找数据比较复杂 遍历列表

CopyOnWriteArrayList

1.内部通过数组实现 初始化容量是0

1
private transient volatile Object[] elements;

2.扩容机制
不存在扩容问题 每次生成一个N+1的数组 将之前的数据拷过来 新的数据追加在后边

1
2
3
4
5
6
public synchronized boolean add(E e) {      Object[] newElements = new Object[elements.length + 1];
    System.arraycopy(elements, 0, newElements, 0, elements.length);
    newElements[elements.length] = e;
    elements = newElements;
    return true;
}

3.线程安全
线程安全 add addAll clear remove都是synchronized方法

Map

1.HashMap
2.HashTable
3.TreeMap
4.LinkedHashMap
5.ConcurrentHashMap
6.ConcurrentSkipListMap

HashMap

1.初始化

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
/**
 * 负载因子 0.75
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 初始化容量为16
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//内部第一层数据结构为数组
transient Node<K,V>[] table; 

//内部第二层数据结构为链表
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

/**
 * >>>为无符号左移 支持负数 -1是为了传进来的数组是4这种 生成一个比传进来的数大的2的幂
 * 111111+1 这样的
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

2.Put方法

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**
 * Implements Map.put and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
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)
        //当前为容量0调用resize方法
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //不存在Hash冲突 直接放进去
        tab[i] = newNode(hash, key, value, null);
    else {
        //存在Hash冲突
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //Value值相等 则直接替换
            e = p;
        else if (p instanceof TreeNode)
            //Next已经为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
                        //如果总数大于7了 转化为树状结构
                        treeifyBin(tab, hash);
                    break;
                }
                //key相等 做替换
                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)
        //size大于推荐容量 需要调用resize
        resize();
    afterNodeInsertion(evict);
    return null;
}

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3.线程不安全

HashTable

1.内部数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    /**
     * 第一层 为数组
     * The hash table data.
     */
    private transient Entry<?,?>[] table;


    //第二层 为链表
    private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
}
  1. put方法
    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
    48
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            //遇到valuse是空 跑抛出异常
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            //当前位置存在Hash冲突
            if ((entry.hash == hash) && entry.key.equals(key)) {
                遇到相等的 则替换
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        //当前位置不存在Hash冲突
        addEntry(hash, key, value, index);
        return null;
    }

    private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //重新计算容量
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

3.HashMap和HashTable区别
HashMap是允许key和value为null值的，用containsValue和containsKey方法判断是否包含对应键值对；
HashTable键值对都不能为空，否则报空指针异常。

TreeMap

1.内部实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//通过红黑树实现
private transient Entry<K,V> root;

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;
}

//Key需要实现Comparator方法
public TreeMap() {
    comparator = null;
}

2.不存在扩容问题
3.线程不安全

LinkedHashMap

1.内部实现 继承HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 通过链表记录顺序
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;

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);
    }
}

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 * 支持按照插入或者访问排序
 * @serial
 */
final boolean accessOrder;

2.put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//put方法使用HashMap的put方法 重写了newNode方法 记录了插入顺序
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

ConcurrentHashMap

一个线程安全且高效的HashMap实现 采用了 CAS + synchronized 来保证并发安全性

ConcurrentHashMap内部实现

1.内部实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * The array of bins. Lazily initialized upon first insertion.
 * Size is always a power of two. Accessed directly by iterators.
 * 第一层数据格式为数组
 */
transient volatile Node<K,V>[] table;

//第二层数据格式为链表
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

2.put方法

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    //计算HashKey
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            //初始化table
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //tab中索引为i的位置的元素为null，则直接使用CAS将值插入即可
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //锁住当前Node进行操作
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}