JAVA API

发表于 | 分类于

String

hashCode()

每从前向后 每个字符的ascii码×31+后面一个字符的ascii码，一次迭代

1
2
3
4
5
h 104
e 101
l 108

所以 "hel".hashCode() 是 （104×31+101）×31+108 = 103183
equals()

比较字符串的内容是否相同

重写equals方法，就要重写hashcode方法，因为俩个对象equals为True，那么x.hashcode()==y.hashcode()也必须为True；如果俩个对象的hashcode不相同，那么equals也一定为False。在Object类中，equals和==是完全一致的，也就是默认情况下，equals就是比较俩个对象的内存地址，但是，一些类可以重写equals方法，比如说String类，equals方法是用于判断俩个字符串的值是否相同，但是默认的hashcode使用的是对象的地址进行计算所得的值，如果不修改hashcode，那么俩个内容相同的字符串，由于在内存中的地址不同，则hashcode就不相同。

针对Map类，在使用put方法或者隔天方法对Map容器进行操作时，都需要根据键对象的hashcode计算存储位置，如果重写了equals方法，导致俩个对象的equals结果为True，但是没有重写hashcode，导致hashcode比较结果为False，比如，在HashMap中，get方法如下

1
2
3
4
public V get(Object key) {
     Node<K,V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.value;
}

其中·hash(key)·就是使用key的hashcode。

1
2
Set存储的是不重复的对象，一句hashCode和equals进行判断，所以Set存储的对象必须重写这俩个方法
如果自定对象作为Map的键，那么必须重写hashCode和equals

StringBuilder

StringBuffer

toStringCache

返回最后一次toString的缓存值，和之前的toString中共享char[]内存，节省内存空间

newCapacity(int var1)

将当前容量翻倍并加2，如果超过2^31-1，则OOM,如果大于2^31-1-8,则设置为2^31-1-8,数组需要8字节存储数组长度

capacity()

初始化时存放int则容量就是int的长度，存放String或者CharSequence的时候，会加16作为容量

HashTable

初始容量和加载因子

默认的初始容量是11,加载因子是0.75,表示当元素个数超过容量的0.75的时候，进行扩容，2×原容量+1。加载因子过大，则会导致单个链表的查询时间过长，加载因子过小，会导致占用过多的空间。

数据结构

继承自Dictionary，实现了Map接口。

成员变量如下：

1
2
3
4
5
table 是一个Entry[]数组类型，而Entry实际上就是一个单向链表，哈希表的键值对就是存放在Entry数组中的
count 保存的键值对的数量，可用size()访问
threshold 判断是否调整容量的阈值
loadFactor 加载因子
modCount 记录了这个hashtable的操作次数，实现fail-fast机制
散列冲突：当不同的key产生相同的索引时，就叫哈希碰撞。

将hashtable视为一串槽，当没有哈希碰撞的时候，直接将键值对插入槽中，当发生哈希碰撞但是key不同，在当前槽中建立链接到这个键值对的链接，如下，假设1和4的哈希值一直，则将(4,14)插入后hashtable的结构如下

1
2
|(12,13)|
|(1,13) | --> (4,14)
hash
1
2
3
4
private int hash(Object k) {
      // hashSeed是一个与实例相关的随机值，用于解决hash冲突
      return hashSeed ^ k.hashCode();
}
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
public synchronized V put(K key, V value) {
    // value为null则抛NullPointerException
    if (value == null) {
        throw new NullPointerException();
    }

    /*
     * 确保key在table[]是不重复的
     * 处理过程：
     * 1、计算key的hash值，确认在table[]中的索引位置
     * 2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
     */
    Entry tab[] = table;
    //计算key的hash值
    int hash = hash(key);
    //确认该key的索引位置,将hash值取绝对值，然后再取模
    int index = (hash & 0x7FFFFFFF) % tab.length;
    //迭代，寻找该key，替换
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

    modCount++;
    //如果容器中的元素数量已经达到阀值，则进行扩容操作
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = hash(key);

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

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

HashMap

扰动函数hash
1
2
3
4
static final int hash(Object key){
	int h;
	return (key == null)?0:(h = key.hashCode())^(h >>> 16)
}