概念

抽象工厂模式 提供了一种方式封装一组独立的工厂有一个共同的主题，而无需指定他们的具体类，即提供接口，用于创建相关或依赖对象的类。

举例

之前提到了 工厂方法模式，区分这两种模式的点在于 工厂方法 -> 单一产品，而 抽象工厂 -> 产品族，对于下面的例子，组件工厂类可以抽分为两种工厂，分别为生成高质量组件的工厂(HighQualityFactory) 和 生成廉价组件的工厂(LowQualityFactory)，工厂生成的是产品族，一个工厂可以生成多种类别的组件，根据组件的高质量 或 廉价 两种属性确定对应的工厂。

概念

定义一个创建对象的接口，但让实现这个接口的类来决定实例化哪个类。工厂方法让类的实例化推迟到子类中进行。

举例

使用了工厂方法模式，最大的优点就是当我们需要一个类对象时，只需要通过将我们需要的条件告诉具体的实现工厂，工厂就会返回给我们需要的对象，将对象封装在工厂中。同时，当具体产品类型增加时，我们只需定义该类，并告诉工厂我们想要该类对象，工厂就会自动帮我们创建。

数据结构

LinkedHashMap 继承了HashMap,对HashMap进行了增强，通过内部维护了双向链表，使LinkedHashMap拥有了顺序访问的功能，提供了有序性。

1
2
3

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

内部构造

Entry内部维护了 before 和 after 两个entry，用于构建双向链表entry之间的指向关系，同时accessOrder 用于设置LinkedHashMap的读取是按照访问顺序还是插入顺序，通过这个accessOrder属性可以很容易实现 LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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;

// 设置LinkedHashMap的读取顺序
//      false(default)：插入顺序
//      true：访问顺序
final boolean accessOrder;

产生原因

• 在多线程环境下，HashMap在扩容时会产生死循环，而线程安全的HashTable，在涉及多线程的操作都采用Synchronized锁住整个数组表，即所有线程在争夺一个资源，效率很低。

1.7 vs 1.8

• 1.7的 ConcurrentHashMap 采用的是分段锁的设计，底层数据结构是Segment + HashEntry，Segment实现了ReentrantLock，自带锁的功能，每次只锁定对应的Segment，多个线程争夺同个segment时，通过tryLock争夺，锁定的粒度下降了，性能也就提高了不少。

• 1.8的ConcurrentHashMap 摒弃了分段锁的概念（Segment），沿用了HashMap的思想，基于数组 + 链表 + 红黑树，底层采用的Node + CAS + Synchronized，保证并发的安全性，锁住的是粒度更小的Node。

分析

内部类Node, 实现了Map.Entry，用于存储键值对，节点用 volatile修饰，保证了多线程间的可见性，同时注意 value也用volatile修饰，无法通过setValue设置value变量。

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

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    /**
     * Virtualized support for map.get(); overridden in subclasses.
     */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

最近在刷 LeetCode 时，看到一道关于位运算的算法题

不使用运算符 + 和-，计算两整数a 、b之和 归根到底，就是运用计算机底层原理，通过位运算进行运算。

加法
思路：用异运算构造两个数的和（不包含进位），用与运算再左移构造两者和的进位数，通过递归直到不进位。

特征

• 根据键的 hascode 值存储数据，可直接定位值，具有很快的数据访问数组
• 遍历的顺序不确定
• 最多允许一条 null 键，允许多条记录的键为 null
• 非线程安全
  可使用 Collections.synchronizedMap 使 HashMap 具有线程安全的能力 或 ConcurrentHashMap

底层结构

底层结构采用了数组，而数组的每一个元素都是多个 Node 构成的链表，当数组超过 threshold 时，数组将会扩容。

数组中的每一个都相当于一个单向链表，key 通过 hash() 后，相同的键值对会加入到链表中，当桶中的数过多时（链表长度 > 8），将会转化为 红黑树，相比与Jdk 1.7， Jdk 1.8 中当链表过长时，链表转化为红黑树，在维护红黑树时，最坏情况下查找的时间复杂度为 O(log n)，比起单链表的 O(1) ~ O(n), 时间复杂度降低了，但所需要维护的空间占用却更多。

ArrayList 是平时常用的数据存储结构，它基于动态数组，支持随机访问，值得一提的是：它是不安全的。造成这种不安全的原因主要是：在在多线程环境下，向 ArrayList 添加或移除时，会产生数组越界等问题。推荐使用 Vector、CopyOnWriteArrayList 代替。

ArrayList 与 Array 区别：

• Array 包含的是基本类型和对象类型，而ArrayList 只能包含对象类型
• Array 的大小的是固定的，所以在定义数组的时候尽量确定需要的数组大小，而ArrayList 的大小是动态变化的，当容量不足时能自动扩容
• ArrayList 可以看作Array的增强版，提供了更多的方法和特性，在查找等操作上更方便

定义

1
2

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

花了一上午时间，通过参照 Hexo 的文档和各种 网上资料 ，终于将博客搭建起来， 由于没仔细参照文档，耽误了好多时间。期间接触到了 Markdown 这种写作语法，写起来还是挺轻便的。以后的新博客都写在这里，旧的博客不再更新。