Container With Most Water

11. Container With Most Water

Difficulty: Medium

Given _n_ non-negative integers a1, a2, …, an, where each represents a point at coordinate (_i_, ai). _n_ vertical lines are drawn such that the two endpoints of line _i_ is at (_i_, ai) and (_i_, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and _n_ is at least 2.

求从数组中，选两个高作为边界，形成一个桶，能装的水最多

如 [6,1,1,4,3,6] 结果是30

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxArea(int[] height) {
        int i=0,j = height.length-1;
        
        int maxA = 0;
        while(i<j){
            int h=Math.min(height[j],height[i]);
            int s = h*(j-i);
            if(s>maxA){
                maxA = s;
            }
            // 如果左边不是更高的，移动左边
            while(height[i]<=h&&i<j){
                i++;
            }
            
            while(height[j]<=h&&i<j){
                j--;
            }
        }
        return maxA;
    }
}

展开全文 >>

Palindrome Number

9. Palindrome Number

Difficulty: Easy

Determine whether an integer is a palindrome. Do this without extra space.
判断一个数字是否为回文数，不使用额外的空间

Some hints:

Could negative integers be palindromes? (ie, -1) 负数不是

If you are thinking of converting the integer to string, note the restriction of using extra space. 如果把数字转为字符串，就不满足不使用额外空间

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?
直接把数字反转，可能会超出空间
There is a more generic way of solving this problem.

My Solution

以12321为例

rev    0        1        12
x    12321    1232    123

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isPalindrome(int x) {
        if(x<0 || (x!=0&& x%10==0))return false;
        if(x<10)return true;
        int rev = 0;
        
        while(x>rev){
            rev = rev*10 + x%10;
            x = x/10;
        }
        return (x==rev || x==rev/10); // 如果数字是偶数，就是x==rev
    }
}

展开全文 >>

Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Difficulty: Medium

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1
2
**Input:**Digit string "23"
**Output:** ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

My Solution

直接用一个递归解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    String digits;
    List<String> l = new ArrayList<>();
    private String[] letter = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        this.digits = digits;
        get("", 0);
        
        return l;
    }
    
    public void get(String temp, int current){
        if(current>this.digits.length()-1){
            if(temp.length()>0)l.add(temp); // 记得判断空的输入
            return;
        }
        
        String value = letter[digits.charAt(current)-'0'];
        for(int i=0;i<value.length();++i){
            get(temp+value.charAt(i), current+1);
        }
    }
}

展开全文 >>

3Sum Closest

16. 3Sum Closest

Difficulty: Medium

在数组中找出和target最接近的三个数的和

Given an array _S_ of _n_ integers, find three integers in _S_ such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2\. (-1 + 2 + 1 = 2).

My Solution O(n^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
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result = Integer.MAX_VALUE;
        int min = result;
        Arrays.sort(nums);
        
        for(int i=0;i<nums.length-2;++i){//length-2,至少有三个数
            int j = i+1, k = nums.length-1;
            // 一个从i后面的位置开始遍历，一个从最后的位置开始遍历
            while(j<k){
                int d = target-nums[i]-nums[j]-nums[k]; // 相加
                if(Math.abs(d)<min){// 
                    min = Math.abs(d);
                    result = nums[i]+nums[j]+nums[k]; // 返回不要写错
                }
                if(d>=0){
                    ++j;
                }else{
                    --k;
                }
            }
        }
        return result;
    }
}

展开全文 >>

3Sum

15. 3Sum

Difficulty: Medium

Given an array _S_ of _n_ integers, are there elements _a_, _b_, _c_ in _S_ such that _a_ + _b_ + _c_ = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

My Solution

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
            
        int length = nums.length;
        Arrays.sort(nums);

        for(int i=0;i<length;++i){
            int j = i+1, k = length-1;
            int target = -nums[i];
            // 避免出现重复解
            if(i>0 && nums[i]==nums[i-1]){continue;}// 这里不要++i,直接跳过就行

            while(j<k){
                int sum = nums[j]+nums[k];
                if(sum==target){
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));  
                    --k;++j;
                    // 避免出现重复解
                    while(j<k&&nums[j]==nums[j-1]){
                        ++j;
                    }
                    while(k>j&&nums[k]==nums[k+1]){
                        --k;
                    }
                }else if(sum > target){
                    --k;
                }else{
                    ++j;
                }
            }
        }
        
        return result;
    }
}

展开全文 >>

JAVA中的反射机制

类的加载机制

  • 装载：通过类的全限定名获取二进制字节流（二进制的class文件），将二进制字节流转换成方法区中的运行时数据结构，在内存中生成Java.lang.class对象。这个时候该类型没有被分配内存，设置默认值，也没有初始化。

  • 链接：执行下面的校验、准备和解析步骤，其中解析步骤是可以选择的；

    • 校验：检查导入类或接口的二进制数据的正确性；（文件格式验证，元数据验证，字节码验证，符号引用验证）

    • 准备：给类的静态变量分配并初始化存储空间；

    • 解析：将常量池中的符号引用转成直接引用；

  • 初始化：激活类的静态变量的初始化Java代码和静态Java代码块，并初始化程序员设置的变量值。

反射机制获取类有三种方法

1
2
3
4
5
6
7
8
9
10
//第一种方式：  
Class c1 = Class.forName("Employee");  
//第二种方式：  
//java中每个类型都有class 属性.  
Class c2 = Employee.class;  
   
//第三种方式：  
//java语言中任何一个java对象都有getClass 方法  
Employee e = new Employee();  
Class c3 = e.getClass(); //c3是运行时类 (e的运行时类是Employee)

java中Class.forName和classLoader的区别

java中class.forName和classLoader都可用来对类进行加载。前者除了将类的.class文件加载到jvm中之外，还会对类进行解释，执行类中的static块。

而classLoader只干一件事情，就是将.class文件加载到jvm中，不会执行static中的内容,只有在newInstance才会去执行static块。Class.forName(name, initialize, loader)带参函数也可控制是否加载static块。并且只有调用了newInstance()方法采用调用构造函数，创建类的对象 

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
class Test{
    static{
        System.out.println("static block");
    }
}

public class Reflect extends ClassLoader{

    public static void main(String[] args) {
        try {
            System.out.println("Class.forName false");
            Class.forName("Test", false, new Reflect());
            System.out.println("Class.forName true");
            Class.forName("Test");

            System.out.println("ClassLoader.loadClass false");
            new Reflect().loadClass("Test");
            System.out.println("ClassLoader.loadClass true");
            new Reflect().loadClass("Test", true);
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }

    }
}

输出结果

Class.forName false
Class.forName true
static block
ClassLoader.loadClass false
ClassLoader.loadClass true

总结

Class.forName可以选择是否初始化，默认为初始化，可以自己选择classLoader

classLoader不能初始化，只能选择是否进行链接，默认不链接。自己本身作为classLoader

参考：

http://blog.csdn.net/liujiahan629629/article/details/18013523

http://blog.csdn.net/u011202334/article/details/51497998

https://www.cnblogs.com/clarke157/p/6651195.html

展开全文 >>

Valid Parentheses

20. Valid Parentheses

Difficulty: Easy

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

括号匹配，使用栈即可

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i);
            if(c == '['||c=='{'||c=='('){
                st.push(c);
            }else if(!st.empty() && c == map.get(st.peek())){
                st.pop();
            }else{
                return false;
            }
        }
        return st.empty();
    }
}

一个不用Map的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}

展开全文 >>

Longest Common Prefix

14. Longest Common Prefix

Difficulty: Easy

Write a function to find the longest common prefix string amongst an array of strings.

求一堆数组的最长公共前缀

思路

这里，采用了从完整字符串往前遍历，一步一步缩小前缀的长度

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0)return "";
        String pre = strs[0];
        for(int i=0;i<strs.length;++i){
            while(strs[i].indexOf(pre)!=0){
                pre = pre.substring(0, pre.length()-1);
            }
        }
        return pre;
    }
}

展开全文 >>

Mission Improbable

4950: [Wf2017]Mission Improbable

Time Limit: 1 Sec Memory Limit: 1024 MB

题目

Mission Improbable原题链接

upload successful
大概意思就是有一堆箱子，在保持最终三视图不变的情况下，求出最多能移走多少个箱子

Input

第一行包含两个整数r(1≤r≤100)和c(1≤n≤100),分别表示网格的行数与列数。
接下来r行,每行包含c个整数,表示对应行上每堆立方体箱的高度(箱子的数量)。
所有的高度在0到10^9之间 (含边界) 。

Output

输出在不被发现的情况下最多能偷走多少箱子。

Sample Input

1.in

5 5 
1 4 0 5 2 
2 1 2 0 1 
0 2 3 4 4 
0 3 0 3 1 
1 2 2 1 1

2.in

2 3 
50 20 3 
20 10 3

Sample Output

1.out

9

2.out

30

思路

以2.in为例
1、首先，把所有箱子都移走。

0 0 0
0 0 0

2、对于俯视图，我们要保证有箱子的地方不能为空，因此在不为空的位置，都放上一个箱子

1 1 1
1 1 1

3、把行和列的最大值位置箱子放上去

50 20 3
20 1  1

4、遍历箱子，如果当前位置不为空，并且这个位置对应行和列的高度相同，说明放这个位置可以同时满足行和列的需求，只要放一次就行了，相当于3多放了一次，我们要尽可能地去重复，利用匈牙利算法去重，让横纵轴最多匹配一次。

50 1  3
1 20  1

5、对去重之后还剩下的重复点，把对应的箱子数加回来

Python代码

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
# -*- coding:utf-8 -*-
import numpy as np


class Solution:
    """
        ICPC 2007 Problem C 推箱子
    """
    def __init__(self, input_file):
        self.grid = None
        self.w = 0                  # 行数
        self.h = 0                  # 列数
        self.result = 0             # 结果
        self.line = []              # 所有边
        self.max_w = []             # 行的最大值
        self.max_h = []             # 列的最大值
        self.grid = []              # 字符串矩阵
        self.mat = None             # 数值矩阵
        self.right = set()          # 二分图右边
        self.right_matched = []     # 标记右侧是否已经被标记
        self.right_match = []       # 标记左边匹配的内容

        self.read_input(input_file)
        self.setup()

    def setup(self):
        """
            获取行列的最大值，把self.grid转为self.mat
            初始化变量
        :return: None
        """
        for i in range(self.w):
            for j in range(self.h):
                self.grid[i][j] = int(self.grid[i][j])
        self.mat = np.mat(self.grid)
        for i in range(self.w):
            self.max_w.append(self.mat[i, :].max())
            # print(self.mat[i, :].max())
        for j in range(self.h):
            self.max_h.append(self.mat[:, j].max())
            # print(self.mat[:, j].max())

        self.line = np.zeros((self.w, self.h))
        self.right_matched = [0]*(self.w+self.h)
        self.right_match = [-1]*(self.w + self.h)

    def read_input(self, input_file):
        """
            读取输入到grid中
        :param input_file:  输入文件路径
        :return: None
        """
        try:
            f = open(input_file, "r")
            first_line = f.readline().replace("\n", "")
            [w, h] = first_line.split(" ")

            self.w, self.h = int(w), int(h)
            self.grid = []
            assert self.w < 101 and self.h < 101
            for i in range(self.w):
                line = f.readline().replace("\n", "")
                self.grid.append(line.split(" "))

        except Exception as e:
            print(e)

    def mission_improbable(self):
        """
            解决推箱子问题
        :return: int 最多可移除的箱子数
        """
        # 遍历矩阵
        for i in range(self.w):
            for j in range(self.h):
                # 移走所有箱子
                self.result += self.mat[i, j]
                # 如果不为空
                if self.mat[i, j] > 0:
                    self.result -= 1     # 俯视图必须要留一块
                    # print("max",i,j, self.mat[i, j], self.max_w[i], self.max_h[j])
                    # 如果这个箱子的位置同时是行和列的最大值，添加到二分图中
                    if self.max_w[i] == self.max_h[j] and self.mat[i, j] > 1:
                        self.line[i, j] = 1
                        self.right.add(j)

        # print("全部移走", self.result)

        # 行的最大值不能移走
        for i in range(self.w):
            if self.max_w[i] > 0:
                self.result -= self.max_w[i]-1
        # 列的最大值不能移走
        for j in range(self.h):
            if self.max_h[j] > 0:
                self.result -= self.max_h[j]-1

        # print("移回行列最大", self.result)

        # 把最大匹配上的加回来
        for i in range(self.w):
            if self.max_w[i] > 0:
                self.right_matched = [0]*(self.w+self.h)
                if self.find(i):
                    # print("find ", i)
                    self.result += self.max_w[i] - 1
        return self.result

    def find(self, i):
        """
            匈牙利算法从i进行搜索
        :param i: 下标，从0开始
        :return: 左边的i是否有匹配
        """
        # 遍历右边
        for r in self.right:
            # print("check ",i," ", r, " ", self.line[i, r])
            if self.line[i, r] == 1 and self.right_matched[r] == 0:
                self.right_matched[r] = 1
                if self.right_match[r] == -1 or self.find(self.right_match[r]):
                    self.right_match[r] = i
                    return True
        return False


if __name__ == '__main__':
    print(Solution("./samples/1.in").mission_improbable())
    print(Solution("./samples/2.in").mission_improbable())

相关链接

[1] 匈牙利算法

展开全文 >>

HashMap源码解析

HashMap源码解析

转自： http://blog.csdn.net/tuke_tuke/article/details/51588156

在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

简单说下HashMap的实现原理：

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75(loadFactor)时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

即HashMap的原理图是：

upload successful

一、JDK1.8中的涉及到的数据结构

1 位桶数组

1
transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

经过transient关键字修饰的字段是不能够被序列化的

2 数组元素Node<K,V>实现了Entry接口

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
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 单向链表的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)// 和自身比较返回true
            return true;
        if (o instanceof Map.Entry) { 	// 强转为Entry类型，key和value都相同才返回true
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

3 红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

    略
}

二、源码中的数据域

加载因子（默认0.75）：为什么需要使用加载因子，为什么需要扩容呢？

因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率

HashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {  
    private static final long serialVersionUID = 362498820763181265L;  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 初始容量，必须是2的幂 
    static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比
    
    //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树  
    static final int TREEIFY_THRESHOLD = 8;  
    static final int UNTREEIFY_THRESHOLD = 6;  
    static final int MIN_TREEIFY_CAPACITY = 64;  
    transient Node<k,v>[] table;//存储元素的数组  
    transient Set<map.entry<k,v>> entrySet;  
    transient int size;//存放元素的个数  
    transient int modCount;//被修改的次数fast-fail机制  
    int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容   
    final float loadFactor;//填充比（......后面略）

三、HashMap的构造函数

HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map

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
// 指定容量和填充比
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
// 指定容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 通过map来初始化
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

四、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
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果出现hash冲突
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 遍历 链表或红黑树，直到找到key相同的
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

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
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
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * 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)
        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)))) // 如果第一个结点就是要找的值
            e = p; 
        else if (p instanceof TreeNode) // 如果已经拓展为红黑树，调用红黑树的put方法
            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
                        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)
        resize();// 扩容
    afterNodeInsertion(evict);
    return null;
}

五、扩容机制

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

六、JDK1.8使用红黑树的改进

upload successful

如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。

它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

相关阅读

HashTable和HashMap的区别详解

HashMap扩容机制

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家