发表于 | 分类于 | 阅读次数: ℃
字数统计: 1.9k | 阅读时长 ≈ 9

HashMap源码浅析

jdk11，工具idea

一、存储结构

入口：Ctrl+N查找到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
/**
     * 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(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

初始化时，为一个Node类型的数组，每个元素为一组键值对。

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;

从静态类中的next可以看出，Node为链表结构。即Node数组的每个元素(也可称为桶)都可存储一个链表。

从 JDK 1.8 开始，一个桶存储的链表长度大于 8 时会将链表转换为红黑树。

二、拉链法

1. 源码跟踪

示例：创建一个hashmap，放入3个键值对。

  1. 新建一个HashMap，默认大小为16，且都为2的幂。
1
2
3
4
/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  1. 将map中放入3个键值对。
1
2
3
4
5
6
7
8
@Test
public void testHashMapHashCode() {
    HashMap<String, String> map = new HashMap<>();
    map.put("K1", "V1"); // hash=2374
    map.put("K2", "V2");
    map.put("K3", "V3");
    System.out.println(map.get("K1").hashCode());
}
1
2715

存入map的键值的哈希值并不等于取出时的哈希值

  1. 确定桶的下表位置(即数组下标)，跟踪put(k,v)源码：

存入K1,V1

1
2
3
public V put(K key, V value) { // K1,V1
    return putVal(hash(key), key, value, false, true);
}
  1. 计算k1的hash=2374
1
2
3
4
5
static final int hash(Object key) { // k1
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // hash=2374
}
  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
49
50
51
52
53
// 参数=2374,k1,v1,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; // 16
    // 计算出桶的索引
    // 如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // i=6
    // 冲突
    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);
                    // 如果冲突的节点数达到8个
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果tab为空或小于64-->resize()
                        // 大于64转为红黑树结构replacementTreeNode               
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果有相同的key值就结束遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 链表上有相同的key值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 大于门限threshold (capacity * load factor)
    if (++size > threshold)
        resize(); // 扩容
    afterNodeInsertion(evict);
    return null;
}
  • 后续操作很多源码从putVal展开

  • 注意索引的取值方法 i = (n - 1) & hash，表示该位置原来没有桶时，新链表的位置

  • K1,K2,K3存入的hash值分别为2374，2375，2376，对应的下标依次为6，7，8

2. put方法

2.1 头插法

当桶下标相同时，后一个put的KV对插在前一个KV对的前面，即新链表插在旧链表的头部。

步骤：

  • 计算K所在的桶下标

  • 确定桶后，在链表在顺序查找，时间复杂度与链表长度成正比。

2.2 null值

在计算hash值时，空值处理 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);即hashmap可以插入null值，但null没有hashCode()方法，就无法计算桶下标，因此以第0个桶确定为null的位置。

3. 扩容

如何理解算法时间复杂度的表示法

假设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。

为了降低复杂度，需要N/M尽可能大，因此M尽可能大。HashMap根据键(N)的数量动态调整table数组(M，Node<K,V>[] table)的长度，即动态扩容。

满足++size > threshold条件时，进行扩容，调用resize()方法

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
/**
 * 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.
 */
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 旧表的两倍
    }
    // 旧表的长度的是0
    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;
}
  • 扩容时须要拷贝旧表到新表，因此很耗时
  • 为提高扩容性能，处理碰撞，jdk1.8后，一个桶存储的链表长度大于 8 时会将链表转换为红黑树
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
/**
  * Replaces all linked nodes in bin at index for given hash unless
  * table is too small, in which case resizes instead.
  */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
 ......

/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    // 父节点
    TreeNode<K,V> parent;  // red-black tree links    
    // 左子树
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
....

发表于 | 分类于 | 阅读次数: ℃
字数统计: 1.4k | 阅读时长 ≈ 5

异常处理问题分析

异常如何处理

问题引入

针对代码中的异常，常规有两种处理方式，一种throws直接抛出，另一种try..catch捕获。

在java项目中，有可能存在人为逻辑的异常，也可能为取得异常的详情，或是保证程序在异常时继续向下执行，会采用第二种处理方式。

但是，代码中每一处异常都来捕获，会使代码什么冗余且不利于维护。

解决思路

定义一个全局异常处理类，返回统一规范的异常信息；

处理逻辑是，先判定是否会出现异常，再执行后续具体的业务。

业务举例

本文主要为了实现全局异常处理的逻辑，只举简单业务

某公司部门需增加员工，处理流程：1先根据员工编号查询员工对象，2判断员工对象是否有信息，即是否不为空，3若有信息，则说明已存在，无需再添加，若不是，则直接添加。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MyService {
    // 注入dao层
    @Autowired
    EmployeeecMapper employeeecMapper;

    /**
     * 添加员工信息
     * @param employee 员工对象
     * @return 影响的行数
     */
    public int add(Employee employee) {
        // 根据id查询员工对象
        Employeeec emp = employeeecMapper.selectByPrimaryKey(employee.getId());
        // 判断是否已有该员工
        if (emp != null){
            // 已有，抛出异常，异常信息为已有该员工
            throw new RuntimeException("异常代码：1201，错误信息：该员工已存在");
        }
        // 没有，插入该员工
        return employeeecMapper.insert(emp);
    }
}

异常处理流程

业务中存在运行时异常和业务逻辑异常，前者不运行时很难察觉，后者在遍及业务时就可以定义出来，因此异常分为不可预知异常和可知异常。流程如下：

  1. 自定义全局异常类，使用@ControllerAdvice，控制器增强
  2. 自定义错误代码及错误信息，两种异常最终会采用统一的信息格式来表示，错误代码+错误信息。
  3. 对于可预知的异常由程序员在代码中主动抛出，由SpringMVC统一捕获。
  4. 不可预知异常通常是由于系统出现bug、或一些外界因素（如网络波动、服务器宕机等），异常类型为RuntimeException类型（运行时异常）。

可知异常

定义异常信息类，变量为错误代码和错误信息，捕获自定义异常时，直接将该对象返回

不可知异常

定义一个map，将常见的异常存入其中，并定义错误代码。对于其他不常见的异常，即map中没有的，同一一个异常对象返回即可。

异常处理代码流程

可知异常

1、定义打印异常信息与返回结果的接口

1
2
3
4
5
6
7
8
9
10
public interface ResultCode {
    // 操作是否成功
    boolean success();

    // 操作结果代码
    long code();

    // 提示信息
    String message();
}
1
2
3
4
public interface Response {
    public static final boolean SUCCESS = true;
    public static final int SUCCESS_CODE = 10000;
}

2、定义打印异常信息的枚举类和返回结果类

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
@ToString
public enum  CommonCode implements ResultCode {
    NO_PAGE(false,404,"没有信息"),
    FAIL(false,500,"操作失败！"),
    SUCCESS(true,200,"操作成功！");

    // 结果信息
    boolean success;
    long code;
    String message;
    
    // 带参构造
    CommonCode(boolean success, long code, String message) {
        this.success = success;
        this.code = code;
        this.message = message;
    }

    @Override
    public boolean success() {
        return true;
    }

    @Override
    public long code() {
        return code;
    }

    @Override
    public String message() {
        return message;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Data
@ToString
public class ResponseResult implements Response {

    boolean success = SUCCESS;

    long code = SUCCESS_CODE;

    String message;

    public ResponseResult(ResultCode resultCode){
        this.success = resultCode.success();
        this.code = resultCode.code();
        this.message = resultCode.message();
    }
}

3、定义错误异常类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class CustomException extends RuntimeException{

    @Autowired
    ResultCode resultCode;
    
    // 带参构造
    public CustomException(ResultCode resultCode){
        this.resultCode = resultCode;
    }
    
    // getter
    public ResultCode getResultCode(){
        return resultCode;
    }
}

4、定义异常抛出类

1
2
3
4
5
6
7
public class ExceptionCast {

    // 静态方法
    public static void cast(ResultCode resultCode){
        throw new CustomException(resultCode);
    }
}

5、定义异常捕获类，使用ControllerAdvice控制器增强的注解，并在捕获CustomException异常的方法上加ExceptionHandler注解，即可捕获该类的所有异常，返回json数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@ControllerAdvice 
public class ExceptionCatch {

    /**
     * 捕获CustomException类异常
     * @param customException
     * @return 结果信息,json数据
     */
    @ExceptionHandler(CustomException.class)
    @ResponseBody
    public ResponseResult customException(CustomException customException){
        ResultCode resultCode = customException.getResultCode();
        return new ResponseResult(resultCode);
    }
}

6、在业务中抛出异常

1
2
3
4
5
6
7
8
9
10
11
12
13
public class MyService {

    @Autowired
    EmployeeecMapper employeeecMapper;

    public int add(Employee employee) {
        Employeeec emp = employeeecMapper.selectByPrimaryKey(employee.getId());
        if (emp != null){
            ExceptionCast.cast(CommonCode.FAIL);
        }
        return employeeecMapper.insert(emp);
    }
}

不可知异常处理

1、类似可知异常，先添加错误代码，如

1
UNAUTHORISE(false,510,"没有权限"),

2、在异常捕获类中添加不可知异常的捕获方法。该方法中，定义一个只读的map存储异常类型的错误代码的映射，map中没有的元素，同一用错误代码999来定义。

1
UNKNOWNERROR(false,999,"未知异常"),
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
@ControllerAdvice
public class ExceptionCatch {

    // 定义map，存贮常见错误信息。该类map不可修改
    private static ImmutableMap<Class<? extends Throwable>,ResultCode> EXCEPTIONS;
    // 构建ImmutableMap
    protected static ImmutableMap.Builder<Class<? extends Throwable>,ResultCode> builder = ImmutableMap.builder();

    @ExceptionHandler(CustomException.class)
    @ResponseBody
    public ResponseResult customException(CustomException customException){
        ResultCode resultCode = customException.getResultCode();
        return new ResponseResult(resultCode);
    }

    /**
     * 捕获非自定义类异常
     * @param exception
     * @return
     */
    @ExceptionHandler(Exception.class)
    @ResponseBody
    public ResponseResult exception(Exception exception){
        // 记录日志
        LOGGER.error("catch exception ==> ",exception.getMessage());
        if (EXCEPTIONS == null){
            EXCEPTIONS = builder.build();
        }
        ResultCode resultCode = EXCEPTIONS.get(exception.getClass());
        if (resultCode != null){
            return new ResponseResult(resultCode);
        }else {
            return new ResponseResult(CommonCode.UNKNOWNERROR);
        }
    }

    static {
        builder.put(HttpMessageNotReadableException.class, CommonCode.INVALID_PARAM);
    }
}

完成~~

不可知异常处理

###

发表于 | 分类于 | 阅读次数: ℃
字数统计: 40 | 阅读时长 ≈ 1

你好

你好

你好

csdn

1
2
3
4
5
6
7
8
@Override
public Collection<? extends GrantedAuthority> getAuthorities() {
    List<SimpleGrantedAuthority> authorities = new ArrayList<>();
    for (Role role : roles) {
        authorities.add(new SimpleGrantedAuthority(role.getName()));
    }
    return authorities;
}

发表于 | 阅读次数: ℃
字数统计: 73 | 阅读时长 ≈ 1

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment