发表于

考虑用静态工厂方法代替构造器

概述

提供一个公有的静态工厂方法，返回类的一个实例

例子

1
2
3
public static Boolean valueOf(boolean b) {
    return b ? Boolean.True : Boolean.False;
}

优势

  1. 拥有显式的名称；

用户可以清楚地知道自己需要那个构造函数构造的对象，例如BigInteger(int, int, Random)返回的是素数，但使用静态工厂方法BigInteger.probablePrime会更加明显。

  1. 不必每次调用的时候都创建一个新对象

静态工厂方法可以使用预先构建好的实例，或者将其缓存起来，重复利用。对象受控于静态工厂方法，可以确保它是一个单例。例如Boolean.valueOf这个方法从不创建新的实例。

  1. 可以返回原类型的任何子类型对象

这种灵活性带来的好处是，API可以返回对象，同时又不会使对象的类变成公有的，而且这个类还可以随着每次调用而发生变化。

  1. 在创建参数化类型实例的时候，代码将变得更加简洁

这里主要指的是类型推导。例如，原先的使用可能是：

1
Map<String, List<String>> map = new HashMap<String, List<String>>();

但假如我们有这样一个静态方法：

1
2
3
public static <K, V> HashMap<K, V> newInstance() {
	return new HashMap<K, V>();
}

这样，我们就可以代替上述啰嗦的使用方式：

1
Map<String, List<String>> map = HashMap.newInstance();

缺点

  1. 类如果不含公有或者protected的构造函数，就不能被子类化。
  2. 与其他的静态方法没有任何区别。

发表于

通过私有构造器强化不可实例化的能力

概述

一些工具类可能不希望被实例化，因为实例化对它没有任何含义。诸如Java.lang.Math这种类只含有静态方法和静态域。

方法

企图将这些类实现成抽象类是行不通的，因为子类化之后仍然可以被实例化。可能会误导用户，以为这是为继承而设计的。

但不包含显式的构造器又可能导致编译器生产缺省的构造器。

因此，我们可以让让这个类只包含私有构造函数，同时包含AssertionError，避免内部实例化：

1
2
3
4
5
public class UtilityClass {
    private UtilityClass() {
        throw new AssertionError();
    }
}

发表于

覆盖equals时请遵守通用约定

概述

覆盖equals方法可能会导致严重的错误。

满足下列条件不覆盖equals

  • 类的每个实例本质上是唯一的；
  • 不关心类是否提供了“逻辑相等”的测试功能；
  • 超类覆盖了equals，该方法对于子类也合适；
  • 类是私有或者包级别私有的；

实现equals方法

当类具备自身特有的逻辑相等概念时，并且超类还没覆盖equals以实现期望方式时，我们应该重载equals；

在覆盖equals时，应该满足以下约定：

  • 自反性：x.equals(x)为true；
  • 对称性：x.equals(y)为true时，y.equals(x)也为true；
  • 传递性：x.equals(y), y.equals(z)为true，x.equals(z)也为true；
  • 一致性：如果两个对象相等，那么它们就必需始终保持相等，除非对象被修改了；
  • 非空性：任何对象都不等于null；

实现高质量equals：

  1. 使用==操作符检查“参数是否为对象的引用”；
  2. 使用instanceof检查“参数是否为正确的类型”，类或者类实现的接口；
  3. 把参数转换成正确的类型，要使用instanceof测试；
  4. 对类中的关键域要，检查参数中的域是否与对应的域对应；

发表于

覆盖equals时总要覆盖hashcode

概述

在每个重载了equals方法的类中，也必须重载hashcode方法，这样才能保证HashMap，HashSet之类的征程工作；

约定

  • 如果同一个对象的信息没有被修改，hashcode方法应该始终如一返回同一个整数；
  • 两个对象在equals方法下相等，那么返回的hashcode也应该是相同的；
  • 两个对象在equals方法下不相等，hashcode不一定要不同，但不同的hashcode有助于hashtable的性能；

一个理想的散列函数应该“为不同的对象产生不相等的hash code”：

  1. 把非零常数值保存在result中；
  2. byte, char, short转换为(int)f;
  3. long类型，则计算(int)(f^f>>32);
  4. float类型，则计算Float.floatToInBits(f);
  5. double类型，则计算Double.doubleToLongBits(f)；
  6. 如果是域的对象引用，则递归调用hashcode；
  7. 数组，则把每一个元素递归地调用hashcode方法调用这个值；或者利用Arrays.hashCode方法；

然后迭代地计算result = 31*result+c；

注意：必须排序equals计算中没有用到的域

发表于

避免创建不必要的对象

概述

最好能重用对象，而不是每次需要的时候创建一个功能相同的对象

极端例子

1
String s = new String("test");

这种用法的坏处就是，语句每次被执行的时候都会创建一个新的实例。因此我们可以用字符串常量代替使用：

1
String s = "test";

对于在同一台虚拟机运行的代码，只要它们包含相同的字符串常量，该对象就会被复用。

重用

尽量使用静态工厂方法而不是构造器；

使用静态初始化器创建不会被修改的对象：

1
2
3
4
5
6
7
8
class Person {
    static {
        Calendar gmtCal = Calendar.getInstance(TimeZone.getTimeZone("GMT"));
        /*
        ....
        */
    }
}

autoBoxing

要优先使用基本类型而不是Boxed primitive type，考虑这样的例子：

1
2
3
4
5
6
public static void main(String[] args) {
    Long sum = 0L;
    for (long i = 0; i < Integer.MAX_VALUE; i++) {
        sum += i;
    }
}

由于sum被声明成Long而不是long，这意味着程序构造了2^31个Long实例。

发表于

内部类

内部类(Inner Class)是定义在一个类中的类。

作用

  • 内部类可以访问该类定义的作用域数据，包括私有数据；
  • 内部类可以对同包内的其它类隐藏；
  • 用匿名类实现回调函数；

C++有嵌套类，嵌套类是一种类之间的关系，而不是对象之间的关系。另外，Java内部类能够引用实例化该内部对象的外部类对象。

只有内部类可以设为private的。

使用方法

大多数用法与常规类类似，有一些特殊的语法规则：

1
outerObject.new InnerClass(para);

局部内部类

如果某个内部类只有在某个方法中创建类型时使用一次，那么可以在一个方法中定义局部类：

外部方法访问final变量

局部类不但能访问外部类，还可以访问局部变量。但该局部变量必须是final的。

静态内部类

如果内部类不需要引用外部类对象，就可以把该内部类声明为静态内部类。

在静态方法中new对象的时候，对应的类必须为static。

发表于

最近在学习Java，学习到了一个新的Java特性——代理(Proxy)。代理可以为其它对象实现一种新的控制访问方式，这是Java SE1.3新加的特性。

目的

假如我们希望在运行时创建一个实现了一组给定接口的新类，我们就可以使用代理实现。

模式

代理类可以运行时创建全新的类，这个代理类能够实现指定的接口：

  • 指定接口所需要的全部方法
  • Object类中的全部方法

这个模式首先要让代理类和目标类实现相同的接口，然后客户端在通过代理类调用目标类的时候，代理类会将所有方法调用分派到目标对象上反射执行。分派过程中则可以在前后增加一些想要的功能。

步骤

  1. 通过实现InvocationHandler接口来自定义自己的handler，该接口有一个invoke的方法；
  2. 使用Proxy类的newProxyInstance创建一个代理对象，并将handler传入该对象；
  3. 通过代理对象调用目标方法；

原理

首先来看一个实现例子，这个程序会打印出被调用的参数和名字：

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
import java.lang.reflect.*;
import java.util.*;

public class ProxyTest {
    public static void main(String[] args){
        Object[] elements = new Object[1000];

        for (int i = 0; i < elements.length; i++) {
            Integer value = i + 1;

            InvocationHandler handler = new TraceHandler(value);
            Object proxy = Proxy.newProxyInstance(null, new Class[]{Comparable.class}, handler);
            elements[i] = proxy;
        }

        Integer rand = new Random().nextInt(elements.length) + 1;

        int res = Arrays.binarySearch(elements, rand);

        if (res > 0)
            System.out.println(elements[res]);

    }
}


class TraceHandler implements InvocationHandler
{
    private Object target;

    public TraceHandler(Object t)
    {
        target = t;
    }

    public Object invoke(Object proxy, Method m, Object[] args) throws Throwable
    {
        System.out.print(target);

        System.out.print("." + m.getName()+"(");

        if (args != null)
        {
            for (int i = 0; i < args.length; i++)
            {
                System.out.print(args[i]);

                if (i < args.length - 1)
                    System.out.print(", ");
            }
        }

        System.out.println(")");

        return m.invoke(target, args);
    }
}

/*
Ouput:
500.compareTo(155)
250.compareTo(155)
125.compareTo(155)
187.compareTo(155)
156.compareTo(155)
140.compareTo(155)
148.compareTo(155)
152.compareTo(155)
154.compareTo(155)
155.compareTo(155)
155.toString()
155
*/

通过打印结果可以得知，每次调用代理对象的compareTo方法，都会调用InvocationHandler的invoke方法。这是因为JVM动态生成的代理类生成代理对象时，会传入InvocationHandler实例对象。

然后我们在invoke方法内部通过Method.invoke()方法打印方法名称和参数来进行调用。

特性

代理类只有一个实例域，那就是InvocationHandler。另外，所有的代理类都覆盖了Object类中的方法toString，equals和hashCode。

对于特定的类加载器和预设的一组接口，只能有一个代理类。

发表于

Recurrent Nerual Networks

目的

相比较于CNN，RNN能够更好地序列的信息。比如理解一句话的意思，根据视频输出行为，判断文本的情感等等。前后的输入是有关联的。

结构

RNN的结构中有一个内部状态值\(h_t\)，这个值取决于输入的x和上一次的内部状态值\(h_{t-1}\)。另外权重矩阵W随着时间的向前，是不会发生变化。同时每次的输入都会产生一个输出值\(Y_t\)

结构图如下：

img

RNN的公式如下： \[ Y_t = g(V h_t) \\ h_t = f(UX_t+Wh_{t-1}) \]

truncated backprop

假如数据序列很长，全部训练的话，我们无法全部放到RNN中，因为可能会造成梯度消失或者爆炸的问题，另外内存也容易不足。因此我们可以根据时间步将序列截断，用前一个序列的final states作为后一个序列的initial states。

img

vanilla RNN

只有一层隐藏层的RNN

LSTM

用来缓解梯度消失和梯度爆炸。

原先的RNN只有一个内部隐藏状态h，该状态对于短期的输入非常敏感，因此我们增加一个状态——cell state，即c，让它保存长期的状态。

LSTM将隐藏状态和输入拼接在一起，然后乘以一个巨大的矩阵，得到四个门向量。

  • i：input gate，whether to write to cell；

\[ i_t = \sigma (W_i [h_{t-1},x_t] + b_i) \]

  • f：forget gate，how much do we want to forget；

\[ f_t = \sigma (W_f [h_{t-1},x_t] + b_f) \]

  • o：output gate，how much to reveal cell；

\[ o_t = \sigma (W_o [h_{t-1}, x_t] + b_o) \]

  • g：gate gate，how much to write to cell；

\[ g_t = tanh(W_g [h_{t-1}, x_t] + b_g) \]

cell state的计算公式为：(注意是按元素相乘) \[ c_t = f_t \circ c_{t-1} + i_t \circ g_t \] 至于隐藏状态： \[ h_t = o_t \circ tanh(c_t) \]

发表于

字典

字典在redis中的应用比较广泛，比如redis的数据库，哈希键的底层实现等等

字典的实现

redis的字典用哈希表表示，一个哈希表有多个哈希表结点，每个结点保存一个键值对。

哈希表

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;//哈希表数组，每个元素为指向dictEntry的指针
    unsigned long size;
    unsigned long sizemask;//等于size-1，与哈希值一起决定key应该放在哪个索引
    unsigned long used;
} dictht;

哈希表结点

1
2
3
4
5
6
7
8
9
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;//可用于解决哈希冲突
}dictEntry;

字典

1
2
3
4
5
6
typedef struct dict {
    dictType *type;
    void* privdata;
    dictht ht[2];
    int trehashidx;
}

type属性是一个指向dictType的指针，dictType结构保存了一组用于操作特定类型键值对的函数，实现多台。

pricdata则保存了需要传给那些类型特定参数的可选参数。

ht保存了两个dictht，一般只是用第一个，第二个会在第一个rehash的时候被使用。

trehashidx则是记录了目前是否在进行rehash。

哈希算法

当添加一个新的键值对到字典的时候，程序依次计算出哈希值和索引值，再根据索引值把包含新键值对的哈希表结点加到哈希数组指定索引上面

1
2
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;

ht[x]是因为有可能在第一个字典或者第二个。

另外，redis使用murmurhash2算法来计算哈希值。

解决键冲突

redis解决hash冲突的方法是链地址法，则产生冲突时使用next指针将索引值相同的结点连起来。

rehash

哈希表的负载因子=哈希表已保存的结点数量/哈希表大小

为了使得哈希表的负载因子维持在一个合理的范围内，哈希表需要扩展或者缩小。

步骤为

  1. 为ht[1]分配空间，大小取决于：
  • 扩展：大小为 大于或等于ht[0].used*2 = 2^n
  • 收缩：大小为 大于或等于ht[0].used = 2^n
  1. 将保存在ht[0]的所有键值对rehash到ht[1]上，重新计算哈希值和索引值；
  2. 释放ht[0]，将ht[1]设置为ht[0]，并新创建一个空白ht[1]，为下次rehash做准备

另外，当下列条件满足时，会进行扩展：

  • 服务器目前没有执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于1；
  • 服务器目前正在执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于5；

这是因为这些命令执行时，子进程会运行中，由于写时复制的操作系统特性，过多或者过快地扩展会带来过多的内存写入操作；

当哈希表负载因子小于0.1时，执行收缩。

渐进式rehash

由于哈希表可能非常大，所以不能一次性rehash成功，而是使用渐进式的方法。

步骤如下：

  1. 为ht[1]分配号空间后，dict结构体同时持有两个哈希表；
  2. 然后dict结构的rehashidx记为0，开始rehash；
  3. 进行期间，会逐个将ht[0]的结点rehash到ht[1]，每次成功都会使rehashidx递增一；
  4. 直到rehash完全，rehashidx设为-1，表示完成；

如果此时有新增的键值对，一律保存到ht[1]中。

发表于

简单动态字符串

redis的字符串表示不是使用的像C语言那种以空字符结尾的字符数组，而是自己构建了一种简单动态字符串（simple dynamic string）——SDS。

而一般来说，redis只会在字符串字面量被用在一些无需对字符串进行更改的地方使用C风格的字符串，比如打印日志。

SDS的定义

sds定义在sds.h的sdshdr的结构体中：

1
2
3
4
5
struct sdshds {
    int len; //记录buf数组中已经使用的字节数
    int free; //buf数组中未使用的字节数
    char buf[];//与C字符串一样以空字符结尾的字符数组
}

之所以在SDS中，使用了与C字符串类似的风格，是因为这样可以直接使用C字符串函数库里面的函数，比如要打印字符串，直接使用：

1
printf("%s", s->buf);

SDS与C字符串的区别

要了解两者之间的区别，首先要从结构体入手。

常数复杂度获取字符串的长度

这个比较好理解，因为结构体本身带有长度域，而设置和更新SDS长度的工作又是由SDS的API执行时自动完成的，所以避免了影响redis的性能。

对于C字符串来说，要获取字符串长度，只能逐个遍历，直到遇到了空字符。

杜绝缓冲区溢出

这个也比较好理解。对于一些字符串拼接的操作，如果没有记录字符串长度，无法得知字符串剩余的内存，这样在拼接的时候就可能发生缓冲区溢出。

而SDS的API在使用sdscat函数进行字符串拼接的时候，会先检查SDS的空间是否足够，不足的话，会使用某种分配策略扩展空间。

减少修改字符串带来内存重分配次数

对于C字符串来说，每次增长或者缩短一个字符串，程序都需要对保存该字符串的数组进行一次重新分配内存的工作，一旦没有重新分配，就可能造成内存泄露或者产生缓冲区溢出。而且因为内存重分配涉及到了复杂的算法，并且有可能会执行系统调用，所以通常是比较耗时的操作。

为了避免C字符串的这种缺陷，redis的SDS实现了空间预分配和惰性空间释放两种优化策略。

  1. 空间预分配

这个策略主要用于优化SDS的字符串增长操作，在进行空间扩展时，不仅仅会分配所需空间，还会为SDS分配额外的未使用空间；

  • 如果对SDS修改后，长度小于1MB，那么程序将分配和len属性同样大小的未使用空间。即如果SDS的len变成了13字节，那么整个buf的数组长度将会变成13+13+1=27个字节；
  • 如果对SDS修改后，长度大于1MB，那么程序将会分配1MB的未使用空间；
  1. 惰性空间释放

该策略会使得SDS在缩短长度时，不会马上使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节数记录下来，并等待将来使用

二进制安全

相比C字符串在读到空字符，则认为是字符串结尾，redis的SDS则是用len属性来检验字符串是否结束。这种二进制安全的做法使得redis不仅可以保存文本格式，还可以保存任意格式的二进制数据