java集合实现方式 原

追逐技术的IT人

1.ArrayList

set()方法非常简单，直接对数组的指定位置赋值即可

public E set(int index, E element) {
rangeCheck(index);//下标越界检查
E oldValue = elementData(index);
elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
return oldValue;
}

get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

public E get(int index) {
rangeCheck(index);
return (E) elementData[index];//注意类型转换
}

private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

public E remove(int index) {
rangeCheck(index);//检查index的合法性
modCount++;//修改版本加1
E oldValue = elementData(index);
int numMoved = size - index - 1;//要移动的元素个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //清除该位置的引用，让GC起作用
return oldValue;
}

Node内部类
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;//原来链表为空，这是插入的第一个元素
else
l.next = newNode;
size++;
return true;
}

public void add(int index, E element) {
checkPositionIndex(index);//index >= 0 && index <= size;
if (index == size)//插入位置是末尾，包括列表为空的情况
else{
Node<E> succ = node(index);//1.先根据index找到要插入的位置
//2.修改引用，完成插入操作。
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)//插入位置为0
first = newNode;
else
pred.next = newNode;
size++;
}
}

final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {//删除的是第一个元素
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {//删除的是最后一个元素
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;//let GC work
size--;
return element;
}

get(int index)方法得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
checkElementIndex(index);//index >= 0 && index < size;
return node(index).item;
}

set(int index, E element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改Node中item的值。

public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;//替换新值
return oldVal;
}

3.ArrayDeque

if (e == null)//不允许放入null
throw new NullPointerException();
doubleCapacity();//扩容
}

doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。

private void doubleCapacity() {
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
elements = (E[])a;
tail = n;
}

if (e == null)//不允许放入null
throw new NullPointerException();
elements[tail] = e;//赋值
if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
doubleCapacity();//扩容
}

public E pollFirst() {
if (result == null)//null值意味着deque为空
return null;
elements[h] = null;//let GC work
return result;
}

pollLast()的作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素。

public E pollLast() {
int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
E result = elements[t];
if (result == null)//null值意味着deque为空
return null;
elements[t] = null;//let GC work
tail = t;
return result;
}

public E peekFirst() {
}

peekLast()的作用是返回但不删除Deque尾端元素，也即是tail位置前面的那个元素。

public E peekLast() {
return elements[(tail - 1) & (elements.length - 1)];
}

offerLast(e)向队尾插入元素，失败则返回false
removeFirst()获取并删除队首元素，失败则抛出异常
pollFirst()获取并删除队首元素，失败则返回null
getFirst()获取但不删除队首元素，失败则抛出异常
peekFirst()获取但不删除队首元素，失败则返回null

offerFirst(e)向栈顶插入元素，失败则返回false
removeFirst()获取并删除栈顶元素，失败则抛出异常
pollFirst()获取并删除栈顶元素，失败则返回null
peekFirst()获取但不删除栈顶元素，失败则抛出异常
peekFirst()获取但不删除栈顶元素，失败则返回null

4.HashSet和HashMap:二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap（适配器模式）。HashMap采用Entry<K,V> table[]实现，table中的每一项都是Entry<K,V>的链表，存储了hash值一样的链表，也就是通过冲突链表方式解决问题。将对向放入到HashMap或HashSet中时，有两个方法需要特别关心：hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要@Override hashCode()和equals()方法。出于性能原因，HashMap是非同步的（not synchronized），如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将HashMap包装成（wrapped）同步的：Map m = Collections.synchronizedMap(new HashMap(...));

get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。

final Entry<K,V> getEntry(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
e != null; e = e.next) {//依次遍历冲突链表中的每个entry
Object k;
//依据equals()方法判断是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式为头插法。

void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//自动扩容，并重新哈希
hash = (null != key) ? hash(key) : 0;
bucketIndex = hash & (table.length-1);//hash%table.length
}
//在冲突链表头部插入新的entry
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry（修改链表的相应指针）。查找过程跟getEntry()过程类似。

final Entry<K,V> removeEntryForKey(Object key) {
......
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);//hash&(table.length-1)
Entry<K,V> prev = table[i];//得到冲突链表
Entry<K,V> e = prev;
while (e != null) {//遍历冲突链表
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
modCount++; size--;
if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
else prev.next = next;
return e;
}
prev = e; e = next;
}
return e;
}

HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法。

public class HashSet<E>
{
......
private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
......
return map.put(e, PRESENT)==null;
}
......
}

追逐技术的IT人

day14_DBUtils学习笔记

2018/05/20
0
0
-1-0 Java 简介 java是什么 java简单介绍

Java是一门纯粹的面向对象的高级的平台无关的编程语言 官网介绍: 了解 Java 技术 https://www.java.com/zh_CN/about/ 推荐词条: https://zh.wikipedia.org/wiki/Java https://zh.wikipedia.o...

noteless
2018/07/03
0
0
【转】115个Java面试题和答案——终极列表

2014/09/30
0
0
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

seaicelin
2018/05/25
0
0
Java 8新增特性优缺点

Java 8于今年三月份正式发布了。那么它是否如我们之前所期待的那样呢？下面我们就一一查看Java8新增特性的优缺点吧。 Java 8试图“创新”，根据 微软对这个词的定义，就是把其他框架或语言里...

Emilypz
2015/09/25
662
1

OSChina 周三乱弹 —— 孤独到都和病毒发生了感情了

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @-冰冰棒- ：#今日歌曲推荐# 逃跑计划《一万次悲伤 (Live)》 《一万次悲伤 (Live)》- 逃跑计划 手机党少年们想听歌，请使劲儿戳（这里） 现在...

26分钟前
6
2
test

carmen-ly

1
0
Android webview热门组件agentweb:4.0.2无法自适应的问题

Android webview热门组件agentweb:4.0.2无法自适应的问题 //设置自适应屏幕，两者合用mAgentWeb.getAgentWebSettings().getWebSettings().setUseWideViewPort(true); //将图片调整到适合w...

Gemini-Lin

5
0

5
0
js中的对象创建的模式以及继承模式

3
0