一、阿里面试题

1、HashMap的原理，内部数据结构？

底层使用哈希表（数组+链表），当链表过长会将链表转成红黑树以实现O（logn）时间复杂度内查找

2、讲一下HashMap中put方法过程？

a、对key求hash值，然后再计算下标
b、如果没有碰撞，直接放入桶中
c、如果碰撞了，以链表方式链接到后面
d、如果链表长度超过阈值（TREEIFY_THRESHOLD == 8）,就把链表转成红黑树
e、如果节点已经存在就替换旧值
f、如果桶满了（容量*加载因子），就需要resize

3、HashMap中hash函数是怎么实现的？还有哪些hash的实现方式？

a、高16bit不变，低16bit和高16bit做了一个异或
b、（n-1）&hash --> 得到下标

4、HashMap怎样解决冲突，讲一下啊扩容过程，假如一个值在原数组中，现在移动了新数组，位置肯定改变了，那是什么定位到这个值新数组中的位置；

将新节点加到链表后
容量扩充为原来的两倍，然后对每个节点重新计算哈希值
这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置

5、抛开HashMap，hash冲突有哪些解决办法？

开放地址，链地址法

6、针对HashMap中某个Entry链过长，查找的时间复杂度可能达到O（n）,怎么优化？

将链表转化为红黑树，JDK1.8已经实现了。

二、源码预热

初看HashMap的源码看不懂怎么办呢？

首先想到它是一个数据结构，一个集合。

一个集合，它是要有Collections的接口的。

一个数据结构，都是有数据的存储方式和存储结构的。

比HashMap更加简单的数据结构就是ArrayList和LinkedList，它们的存储结构和存储方式了解吗？

ArrayList的存储方式是数组：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

//transient  不参加序列化的关键词
transient Object[] elementData;

三、源码猜测

四、源码分析

五、源码总结

一、前言：

Java数据结构：HashMap

那么有没有身么结构能够结合两者的优势呢？
有，就是Hash表
Java数据结构：HashMap

二、HashMap常用方法put、get

我们开始学习HashMap，先从常用方法put、get方法学起：

HashMap.java

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

那么 hashcode是什么？有什么作用？

Object.java

public class Object {
	...
	public native int hashCode();
}

由上可见，hashcode是object的基本属性之一。那么它有什么作用呢？

HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的。

具体可见：讲讲HashCode的作用

数组和链表怎么组织工作？

int hash是什么？有什么作用？

Hash的原理是什么？

Hash的put方法原理？

Hash的get方法原理？