面试经常问到的：

面试题

数组  ：

物理上连续的大小确定的存储空间   例如：int[]

优点：快速查找

缺点：动态增删改查，性能差 速度慢

顺序表：

物理上连续，逻辑上连续，大小可以动态增加       例如：ArrayList

ArrayList源码分析：

底层用System.arrayCopy

插入数据原理：要插入数据位置之后的数据全部后移，留出的空位放入要插入的数据。

添加数据

```

    @Override public E remove(int index) {

        Object[] a = array;

        int s = size;

        if (index >= s) {

            throwIndexOutOfBoundsException(index, s);

        }

        @SuppressWarnings("unchecked") E result = (E) a[index];

        System.arraycopy(a, index + 1, a, index, --s - index);

        a[s] = null;  // Prevent memory leak

        size = s;

        modCount++;

        return result;

    }

```

从上面代码可以看出，ArrayList 增加和删除元素都是很耗时的。

应用场景：只展示数据，不做增加和删除。例如聊天记录。

链表 :

物理上不连续，逻辑上连续，可以动态增加和删除节点。  例如：LinkedList

数据结构示意图

增加，插入数据原理：分两步

1. 前一个数据的 next 指向要插入的数据的data ,

2 要插入数据的next 指向下一个数据的 data

删除原理：

将要删除数据的前一个节点的next对象  指向删除数据的下一个节点的data对象   要删除的数据没有引用 会被JVM回收

LinkedList 查询源码

查找需要用 for循环，比较耗时

由此可以看出 增加和删除的速度比ArrayList 速度快

缺点 查找速度慢。

总结

啰嗦了这么多，主角终于要登场了

HashMap

数组+单链表   具备顺序表和链表的优点 。

数据结构图 数据结构

五个问题：

1，数组和链表如何组织工作

2，int hash是什么，有什么用

3，Hash的原理是什么

4 ，put方法原理

5，Hash  get方法原理

Object 类   hashCode方法：

String 和 Integer 都实现了hashCode ，所以适合作为key值

Hash是进行了一些位移运算。

put方法源码

拿key进行Hash运算     然后拿Hash值计算下标   

 int index = hash & (tab.length - 1)     ==   hash %(tab.length - 1);

求模  计算数组下标 不越界。tab 数组下标

线性运算 速度快

不同的key 计算出来的index值 有可能相同，如果相同，追加到当前节点 后面形成单向链表。

if (e.hash == hash && key.equals(e.key))     //  说明key值相同

{ preModify(e); V oldValue = e.value; e.value = value; return oldValue; }     // 覆盖之前的value

说明，HashMap里面key值唯一  不能相同，相同的话，会把之前的值覆盖掉。

get方法源码

get时，计算Hash值和index的方法，和put时 计算方式一样，确保获取的下标时一致的。

static final float DEFAULT_LOAD_FACTOR = .75F;   //加载因子

当链表的长度超过  数组长度* 加载因子  的时候，会扩容 数组长度会变长   变为 原长度*2，以减少碰撞冲突。

能否使用自定义对象作为key

可以，最好让对象重写hashcode方法，以减少冲突。

Android 28 对HashMap进行了优化  链表换成了红黑树。