岁月不饶人，我亦未曾绕过岁月，总结反思，重新来过。

1
后端开发面试总结

哈希

从效率方面考虑，数组的检索效率较好，但是插入和删除效率低下；对于链表，插入和删除的效率较好，但是检索的效率低下，然而 HashMap 合理的继承了上述两位的所有优点，意味着完美。

针对哈希函数的构造

  1. 直接定址法
  2. 平方取中法
  3. 除数余数法

为几种主要的方法，具体不展开论述，对于 HashMap 神奇存储展示拙见

HashMap部分源码分析

  • 感触

HashMap 的数据是存储在 Table 数组中的，是一个 Entry 数组，二维处理的话，纵观为数组，横向为链表，每当建立一个 HashMap 的时候，就初始化一个数组

1
transient Entry[] table;

【解释】transient关键字，为了使其修饰的对象不参与序列化
【实质】此 table 对象无法持久化

【总结】对于HashMap的工作原理的简要阐述（可作为面试参考回答）

HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。 每当往hashmap 里面存放key-value对的时候，都会为它们实例化一个Entry对象，这个Entry对象就会存储在前面提到 的Entry数组table中。Entry具体存在table的那个位置是 根据key的hashcode()方法计算出来的hash值 （来决定）。

  • 定义数组中的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 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> { //Entry数组中的链表
	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;
    }
}
  • 取 Entry ，判断方法为【如果 key==null ，直接取数组的第一个元素，如果不是，先计算出 key 的 hashcode 找到下标，再判断是否相等，如果相等，则返回对应的 entry ，如果不相等，则返回 null 】
1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
  • 扩容

其本质是先新创建一个2倍于原来长度的 table 数组，通过重新遍历将旧的 table 中的数据复制 到新的 table 中，在新的 table 中，索引 hash 值重新计算，并且更新扩容后的阈值。

1
2
3
4
5
6
7
if ((size >= threshold) && (null != table[bucketIndex])) {
// 将table表的长度增加到之前的两倍
resize(2 * table.length);
// 重新计算哈希值
hash = (null != key) ? hash(key) : 0;
// 从新计算新增元素在扩容后的table中应该存放的index
bucketIndex = indexFor(hash, table.length);

其中 resize 起到了创建一个新的 table 数组的作用

针对HashMap的数据存储无序性及其他特性

HashCode

  • 与 equals 的协调合作

hashcode 和 equals 通常是同时出现用来获取值的【在 HashMap 中使用 hashcode() 和 equals() 方法确定键值对的索引】

用法：
初步了解了HashMap的工作原理，在此基础上，如果要在 HashMap 中新增加元素的时候保证不重复，只用 equals 显然不如结合 hashcode方便，可以直接利用此方法将新的数据存储而不进行任何比较，这也就是查找效率高的本质，降低了比较次数。

注意点：
在Java中相等（相同）的对象必须具有相等的哈希码（或者散列码），但是如果两个对象的hashcode相同，它们并不一定相同。没有正确使用的时候会导致相同 hash 值的结果。

  • 方法详解

先看 hashcode 的定义public native int hashcode(); – 证明 hashcode 是一个本地方法【前提是原生的方法而非经过自定义覆盖过的】

hashcode() 方法给对象返回一个 hash code 值，性质有以下几点：

  1. 在一个Java应用执行期间，如果一个对象提供给 equals() 做比较的信息没有被修改的话，该对象多次调用hashCode()方法，该方法返回的 integer 必须相同；
  2. 如果两个对象依 equals() 方法判断是相等的，分别调用 hashcode() 方法产生的值必须相同；
  3. 并不要求依 equals() 方法判断不相等的两个对象，分别调用各自的 hashCode() 方法必须产生不同的 integer 值。然而，对于不同的对象产生不同的integer结果，有可能会提高 hash table 的性能。

LinkedHashMap

我们知道 HashMap 的存储是无序的，那么为了有顺序存储键值对，就需要引入LinedHashMap。【当然检验此句话可以尝试分别输出 HashMap 中存储的值和 LinkedHashMap 中的值】

同样的在 Map 旗下，而且 LinkedHashMap 继承了 HashMap ，在定义的时候稍微变动类名就OK：Map<String, String> = new HashMap<>();
Map<String, String> = new LinkedHashMap<>();

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

所以在用法上，LinkedHashMap 和 HashMap 的用法基本一致，通过 put 和 get 的方法进行 key-value 的存储和读取。

  • 区别点

LinkedHashMap 的有序性到底体现在什么地方？

其本质为 HashMap + 双向链表的组合，即通过 HashMap 的构造函数初始化 Entry 数组【图左】，然后通过LinkedHashMap 自身的 init 的初始化方法初始化了一个只有头节点的双向链表【图右】。

有了双向链表的存在，那么在进行 put /扩容等操作时就需要考虑到双向链表的事。

  1. 在 put 元素时，不但要把它加入到HashMap中去，还要加入到双向链表中；【记住一点：header 并不能存储数据】
  2. 扩容时，数据的再散列和HashMap是不一样。

① HashMap 是先遍历旧 table ，再遍历旧 table 中每个元素的单向链表，取得 Entry 以后，重新计算 hash 值，然后存放到新 table 的对应位置；

② LinkedHashMap 是遍历的双向链表，取得每一个 Entry ，然后重新计算hash值并且存放到新 table 的对应位置。

附上一个较为详细的解释：https://www.jianshu.com/p/8f4f58b4b8ab

ArrayList

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

ArrayList 是可以动态增长和缩减的索引序列，它是基于数组实现的List类

ArrayList 的应用在于其的可变长性，本质是类对象内部定义了 capacity 属性，封装了一个动态再分配的 Object[ ] 数组，当数组的元素数量增加时，属性的值会自动增加。

如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capcacity，可以减少增加重分配的次数提高性能 。

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
/**
 * Default initial capacity.
 *
 */
 	private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
    private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


/**
 * Increases the capacity of this <tt>ArrayList</tt> instance, if
 * necessary, to ensure that it can hold at least the number of elements
 * specified by the minimum capacity argument.
 *
 * @param   minCapacity   the desired minimum capacity
 */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            //DEFAULT_CAPACITY;//这里的值为10

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

ArrayList 和 vector 的区别

线程

ArrayList 线程是不安全的, vector 的线程是安全的
当多线程访问一个 ArrayList 时,需要手动保持同步性

ArrayList 底层实现

底层的数据结构就是数组，本质是 elementData，数组元素类型为Object类型，即可以存放所有类型数据【包括 null 】，所有的操作都是基于数组的。

ArrayList 继承了 AbstractList，AbstractList 继承了 AbstractCollection

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

private void grow(int minCapacity) {
	// overflow-conscious code
    //将扩充前的elementData大小给oldCapacity
    int oldCapacity = elementData.length;
    //newCapacity就是1.5倍的oldCapacity，因为向右移1位代表除以2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    /**
    *这句话就是适应elementData空数组的时候，length=0
    *那么oldCapacity=0,newCapacity=0,所以这个判断成立
    *在这里就是真正的初始化elementData的大小了，前面的工作都是准备工作。
    */
     	newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    //如果newCapacity超过了最大的容量的限制，就调用hugeCapacity，也就是能给的最大值给newCapacity
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //新的容量大小已经确定好了，就copy数组，改变容量大小
    elementData = Arrays.copyOf(elementData, newCapacity);
}

grow() 方法是 ArrayList 的核心，该方法保障了变长特性。

附上一个底层方法个详解：https://blog.csdn.net/weixin_42036647/article/details/100709820

ArrayList 和数组的区别

数组

优点：在内存中的存储时连续的，索引速度快，赋值和修改也较为方便

缺点：数组中插入元素比较繁琐，而且在定义时需要指定元素类型和数组长度

ArrayList

优点：解决了数组的缺点

缺点：在插入元素时，可以插入任意元素，都被处理为 Object 类，但是不保证数据安全，在数据利用的时候会报类型不匹配的错误

从时间复杂度的角度分析 ArrayList：https://blog.csdn.net/weixin_33939380/article/details/87975097

+= 是如何实现的

1
2
3
4
5
6
7
8
9
C/C++ code

template <class T> 

const T operator+=(const T& rhs) 

{ 
    return *this + rhs;                
}

所以对于 += 运算符，在使用过程中不会申请新的内存。

由于运算符优先级不同，i = i + 1 的运算速度要低于 i += 1
【优先级标准：优先级从上到下依次递减，最上面具有最高的优先级，逗号操作符具有最低的优先级。表达式的结合次序取决于表达式中各种运算符的优先级。优先级高的运算符先结合，优先级低的运算符后结合，同一行中的运算符的优先级相同。】

字符串

在 Java 中字符串 String 是不可改变的，通过操作运算符改变后返回的是新对象，并不能将原有字符串改变

原因：

1)字符串变量是存放栈内存中的，而其所对应的字符串是存放在堆内存中的。

2)某个字符串变量一旦赋值，实际上就是在栈内存中的这个字符串变量通过内存地址指向到堆内存中的某个字符串。

3)而如果这个字符串变量所对应的字符串发生改变，在堆内存中就会新款开辟一块空间出来存放这新字符串，并使得原先的内存地址指向发生改变

对于之前的字符串，如果不再有其他字符串变量所指向，那么将会变成垃圾，交由 Java 中的 GC 机制进行处理。

【注意：无论对字符串变量进行重新赋值、截取、追加等操作其实改变的都不是字符串本身，而是指向该字符串的内存地址。】

字符串 string 转 Int

在 Java 中 Integer 类型下有名为 parseInt() 的方法，专门用于将字符串参数作为有符号的十进制整数进行解析【如果方法有两个参数， 使用第二个参数指定的基数，将字符串参数解析为有符号的整数。】

实现 parseInt() 方法：

  1. 使用 map 字典的形式存储从 0~9 十位数字分别对应的字母，进行字符串的切割组合
  2. 直接进行每一位字符的转换组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int parseInt(String num) {
	int index = 0;
	int result = 0;

	if (num.startsWith("-")) {
		index++;
	}
	while (index <= num.length() - 1) {
		int n = num.charAt(index);
		if (n <= 57 && n >= 48) {
			result *= 10;
			result += n - 48;
		} 
		else {
			System.err.println("args is not a interger");
		}
		index++;
	}
	if (num.startsWith("-")) {
		result = -result;
	}
	return result;
}