# 算法：列表List、映射Map、集合Set-理论

## 列表List

### Java中的list是怎么实现的？

Java中ArrayList的添加元素方法，简要分析

```package java.util.ArrayList;
transient Object[] elementData;             // non-private to simplify nested class access
public ArrayList() {                        //构造函数
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private int size;
public boolean add(E e) {                                                    //添加方法
ensureCapacityInternal(size + 1);                                         //必要检查步骤，如下 下标、数组大小
elementData[size++] = e;                                                 //实际存入数组中
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static int calculateCapacity(Object[] elementData, int minCapacity) {//检查数组下标
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                  //首次返回1
return Math.max(DEFAULT_CAPACITY, minCapacity);                      //int DEFAULT_CAPACITY=10
}
return minCapacity;                                                      //后续返回当前值
}

private void ensureExplicitCapacity(int minCapacity) {                       //检查是否需要扩容数组
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)                                //当前下标是否大于数组已有长度
grow(minCapacity);                                                  //自动扩容
}

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);            //拷贝数组，增加长度
}```

## 映射Map

### Java中的Map是怎么实现的？

Java中HashMapt的添加元素方法，简要分析

```     package java.util.HashMap;
static final float DEFAULT_LOAD_FACTOR = 0.75f;                    //在构造函数中未指定时使用的加载因子

static class Node<K,V> implements Map.Entry<K,V> {                //感觉是一个具有键值的链表
final int hash;
final K key;
V value;
Node<K,V> next;
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
......  //里面有一些方法getKey、getValue、toString、setValue
}
public HashMap() {                                                //构造函数
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

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

static final int hash(Object key) {                               //获取Key的哈希值
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //调用key的对象哈希值，>>>为无符号右移运算符
}

//第一个参数：Key的哈希值。第二个参数：key。第三个参数：值。
//第四：默认为true，改变key所映射的值。第五个参数：默认为false，哈希表已经创建。
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)          //transient Node<K,V>[] table;
n = (tab = resize()).length;                                //resize()是初始化或加倍表格大小
if ((p = tab[i = (n - 1) & hash]) == null)                 //链表数组是否为空
tab[i] = newNode(hash, key, value, null); //创建具有保存键值的链表并保存数据进去，但是最后一个为null也就不是链表了
else {                                                      //发生哈希冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;                                             //让e非空
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key                //e非空，更改Node对象的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)                                        //Node数组不够了
resize();                                                  //扩容
afterNodeInsertion(evict);                                     //默认true
return null;
}```

## 集合Set

### Java中的Set是怎么实现的？

```    package java.util.HashSet;
public HashSet() {                //构造方法
map = new HashMap<>();        //创建一个hashMap保存元素
}

private static final Object PRESENT = new Object();//与后面Map中的对象值关联的虚拟值
public boolean add(E e) {
return map.put(e, PRESENT)==null;              //只传递Key，不传递值
}

//后面map.put(e,obj)的实现，可以看前面map的详细介绍```

0 条评论

• ### 基于 SpringCloud 微服务架构的广告系统（第一部分：eureka、zuul、通用模块）

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### Java的基础程序设计结构（Java学习-1）

注释就是方便自己或者别人阅读代码，绝大多数的程序语言都有注释这个功能，大部分的注释命令都是相同的或者想通的，

• ### 算法：哈希表HashTable-理论

哈希表，我们平时好像用到的不多，使用HashMap的时候，才间接的使用到了，在信息安全领域用到的比较多（文件效验、数字签名），下面我们先来看看哈希函数。

• ### 面试 | Java8 HashMap原理

基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化。

• ### 面试必备：HashMap源码解析（JDK8）

在分析jdk1.8后的HashMap源码时，发现网上好多分析都是基于之前的jdk，而Java8的HashMap对之前做了较大的优化，其中最重要的一个优化就是桶中...

• ### Java 集合源码分析（一）HashMap

附：更这个系列感觉自己像是又挖了一个坑?，不过趁自己刚好工作不太忙，有空闲期，静下心来研究学习源码也是一件很值得做的事，自己尽量会把这个坑填完?。

• ### HashMap源码剖析

HashMap是大家常用的基于哈希表的Map接口实现,这里解说的是JDK1.8的代码,在介绍它之前，我们先来看看编写HashMap代码的是哪几位大牛。

• ### 90%面试都会问到的知识点，你看会吗？

HashTable：线程安全，每个方法都加了 synchronized 修饰。类似 Collections.synchronizedMap(hashMap)

• ### JDK源码分析-HashMap(1)

HashMap 是 Java 开发中最常用的容器类之一，也是面试的常客。它其实就是前文「数据结构与算法笔记（二）」中「散列表」的实现，处理散列冲突用的是“链表法...

• ### HashMap,HashTable,ConcurrentHashMap面试总结！！！

HashTable：线程安全，每个方法都加了 synchronized 修饰。类似 Collections.synchronizedMap(hashMap)