数据结构之容器
一、概述
1.什么是数据结构中的容器？
容器是一种把多个元素组织在一起的数据结构，也可以理解为一种可以包含其他类型对象作为元素的
的对象。容器是仅仅用来存放数据的，本身没有取出元素这种能力，大多数情况下是通过可迭代对象来
操作容器
容器这种数据结构在各种编程语言中都有相应的实现，比如我们经常会比较熟悉的C++的标准模板库
（Standard Template Library，STL）、Java的集合框架（Java Collections Framework，JCF）、而在
Python中更是将容器类型的数据结构作为其基本数据类型、Go语言也有内建的容器和相应的标准库，
本篇博客便是在总结各种容器使用及原理的基础上，对Java、Python中相同的类型的容器做一个横向的
对比，以便于日后的总结和复习
2.Java集合框架简介
（1）泛型的机制
Java中的容器就是可以容纳其他Java对象的对象，且Java容器中只能存放对象，对于一些基本的数据
类型（比如int、long、float、double等），需要将其包装成对象类型之后（Interger、Long、Float、Double
等）才能放到容器里，很多时候拆包装和解包装使能够自动完成的
Java容器能够容纳任何类型的对象，表面上是通过泛型机制完成的。事实上，所有容器的内部存放的都
是Object类的对象，所有的对象都是Object类型的子类。泛型机制只是简化了编程，由编译器自动帮助我们
完成了强制类型的转换而已，示例代码如下
ArrayList<String> list = new ArrayList<String>(); //参数化类型
list.add(new String("csuyzz"));
String name = list,get(0); //容器中存放的Object类的对象隐式转换成为String类型的对象
此外，Java里的对象都在堆上，且对象只能通过引用（reference）来访问，容器里存放的其实是对
象的引用而不是对象的本身
（2）接口和实现（Interfaces and Implementations）
在Java 的集合框架中共定义了14种容器的接口，关系图如下所示，Map接口没有继承自Collection的
接口，因为Map接口是关联式的容器而不是集合，但也可以从Map转换到Coolection；Stack已经被Deque
所取代
接口的实现如下表所示
| Implementations | ||||||
|---|---|---|---|---|---|---|
| Hash Table | Resizable Array | Balanced Tree | Linked List | Hash Table + Linked List | ||
| Interfaces | Set | HashSet | TreeSet | LinkedHashSet | ||
| List | ArrayList | LinkedList | ||||
| Deque | ArrayDeque | LinkedList | ||||
| Map | HashMap | TreeMap | LinkedHashMap | |||
迭代器为我们提供了遍历容器中元素的方法，它只能通过容器本身来得到，迭代器是我们更加方便地去操作
容器，下面是示例：
ArrayList<String> list = new ArrayList<String>();
list.add("csuyzz");
list.add("csu001");
for(String name : list){
System.out.println(name); //使用迭代器进行输出数据
}
二、List
1.Java中的List容器
（1）ArrayList
ArrayList 实现了List接口，元素存放的顺序与放进去的顺序相同，允许放入null元素，底层通过可变数
组来实现。每个ArrayList都有一个容量（capacity）表示底层数组的实际大小，容器内存储的元素的个数
不能大于当前容量；当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的容量。而且这里
的数组是一个Object的数组，可以容纳任何类型的对象
ArrayList与Vector的最大不同就是ArrayList没有实现同步，当多个线程并发访问时，用户可以手动进行
同步，也可以使用Vector来进行替代
对于一些常用的方法，比如size()、isEmpty()、get()、set()时间复杂度为O（1）、add()方法的时间开销
与插入的位置有关，其余均为线性时间
set()方法就是对数组指定的位置赋值，源码实现如下
//Object[] elementData
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]; //类型的转换
}
add（）方法，在尾部追加元素 add (E e)，add（int index，E e）在指定位置插入元素，这两种方法在
执行时都有可能导致容量的不足，实际在添加元素之前，都要进行剩余空间检查，需要时通过grow()方法进
行自动扩容；注意add(int index，E e)需要先对元素进行移动，然后完成插入操作，该方法有着线性的时间
复杂度
remove() 方法有两种，remove( int index )删除指定位置的元素，remove(Object o)删除第一个满足
o.equals(elementData[index])的元素，删除之后需要将删除点之后的元素向前移动一个位置，所以时间
复杂度是O(n)的，但是为了让GC起作用，必须显示的为最后一个位置赋null值
public E remove(int index){
rangeCheck(index); //下标越界检查
modCount++;
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;
}
(2) LinkedList
LinkedList同时实现了List接口和Deque接口，它可以充当顺序容器、队列和栈，但是使用栈或者队列的
首选是ArrayDeque，LinkedList数据的存储方式如下图所示
LinkedList底层通过双向链表来实现，双向链表的每个节点使用内部类Node表示，LinkedList通过first
和last引用分别指向链表的第一个和最后一个元素，不存在哑元，当链表为空的时候first和last都指向null,
LinkedList没有实现同步
//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;
}
}
LinkedList中所有跟下标有关的操作都是O（n）的时间复杂度,在链表的头部和末尾插入和删除元素时都
常数时间
add（）方法有两种，add(E e),在链表的末尾插入元素，常数时间；add（int index，E element）,在指定
的下标处插入元素
//add(E e)方法的实现
public boolean add(E e){
final Node<E> l = last; //将原来最后一个节点赋给l
final Node<E> newNode = new Node<>(l,e,null); //新建节点指向原来最后的节点
last = newNode; //新建节点化成最后一个节点
if(l == null)
first = newNode; //原来的链表为空，这是插入的第一个元素
else
l.next = newNode; //原来最后的节点指向新的最后的节点
size++; //链表的大小增加
return true; //返回插入成功
}
//add(int index,E element)方法的实现
public void add(int index,E element){
checkPositionIndex(index); //判断元素的下标是否在范围内 0 - size
if(index == size) //插入的位置是末尾包括列表为空的情况
add(element);
else{
Node<E> target = node(index); //先根据index找到要插入的位置节点
final Node<E> pred = target.prev;
final Node<E> newNode = new Node<>(pred,element,target);
target.prev = newNode;
if(pred == null) //插入首部节点
first = newNode;
else
pred.next = newNode;
size++;
}
}
remove() 方法：删除跟指定元素相等的第一个元素remove(Obiect o)，remove(int index)删除指定下标
的元素，时间复杂度均为O(n)
//unlink删除一个Node
E unlink(Node<E> x){
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if(prev==null){
first=next; //删除的是第一个元素
}else if(next==null){
last = prev; //删除的是最后一个元素
}else{
prev.next = next;
next.prev = prev;
x.prev = null;
x.next = null;
}
x.item = null ; //删除的节点赋null值使其可以被GC清理掉
size--;
return element;
}
get() 方法，得到指定下标处元素的引用
public E get(int index){
checkElementIndex(index); //验证下标是否合法
return node(index).item;
}
set（）方法：set（int index，E element）将指定下标出的元素修改为指定值
public E set(int index,E element){
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element; //替换成新值
return oldVal;
}
2.Python中的list
Python中list(列表)是其最基本的数据结构，也可以理解为List容器是Python内置的，不像Java那样专门
去写一套集合框架，list底层实现的原理和Java中的ArrayList是非常相似的，这里就不再过多阐述
值得一提的是Python中也有自己的数据结构与工具库，pydu（python data structures and utils）,在这个
工具库中给出了python本身list所不具有的比较强大的功能，以后用到的时候可以查阅
三、栈和队列
1.Java 中的栈和队列
在使用栈和队列时，Java比较推荐使用ArrayDeque，当然也可以使用LinkedList。那么ArrayDeque是如何
既能实现栈，又能实现队列的呢？Deque的含义是 “Double ended queue”，即双端队列，对于双端队列的操
作其实是非常简单的，无非就是对容器的两端进行添加、删除或者查看
ArrayDeque底层是通过数组进行实现的，此外为了满足可以在数组两端插入或者删除元素时，该数组还
必须是循环的，即循环数组。这种的数组的特点就是，任何一点都可能被看做起点或者是终点，head指向首
端第一个有效元素，tail指向尾端第一个可以插入元素的空位；head不一定总等于0，tail也不一定总比head大。
ArrayDeque是非线程安全的
addFirst() ：addFirst（E e）的作用是在deque的首端插入元素的，也就是在head前面插入元素，在
插入的过程中实际要考虑到空间是否够用，下标是否会越界等问题
public void addFirst(E e){
if(e==null) //deque中不允许放入null
throw new NullPointerException();
elements[head = (head - 1)&(elements.length - 1)] = e;//当head为0是插入到最后，解决了数组越界问题
if(head == tail) //判断空间是否足够使用
doubleCapacity(); //扩容 申请一个原数组两倍的数组，在将现有数组复制过去
}
//扩容函数 doubleCapacity()
private void doubleCapacity(){
assert head == tail;
int p = head;
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); //将elements数组从p开始的r个元素放置到a数组中从0开始的地方
System.arraycopy(elements,0,a,r,r,p);
elements = (E[])a;
head = 0; //扩充完成后放置head和tail的节点
tail = n;
}
addLast（E e）函数在Deque插入元素，即在tail的位置插入元素，tail总是指向下一个可以插入的空位，
插入完成后检查空间，如果用光，则需要进行扩容
public void addLast(E e){
if (e == null)
throw new NullPointerException();
elements[tail] = e; //赋值
tail = (tail + 1) % (elements.length-1); //获取tail的新坐标
if(tail == head) //下标越界
doubleCapacity();//扩容
}
pollFirst（） 删除并返回Deque的首端元素，也即是head位置处的元素
public E pollFirst(){
E result = elements[head];
if(result == null) //此时deque的值为空
return null;
elements[head] = null ;//手动赋null值，这样可以使GC工作
head = (head+1) & (elements.length -1); //下标越界处理
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 ; //GC
tail = t;
return result;
}
peekFirst() 的作用是返回但是不删除Deque首端的元素，也即是head位置处的元素
public E peekFirst(){
return elements[head]; //如果队列为空，则会返回null
}
peekLast() 返回但不删除Deque尾端的元素，即tail位置前面的那个元素
public E peekLast(){
return elements[(tail -1)& (elements.length - 1)];
}
2.Python中的栈和队列
与Java非常的类似，Python在栈和队列方面也有自己的轮子，collections模块中的deque也是一个双向
队列，它的使用与ArrayDeque非常相似，它的底层实现的原理与list是相同的
#对于deque数据结构的示例操作
import collections
douqueue = collections.deque() #创建一个双端队列
douqueue.append() #往右边添加一个元素
douqueue.appendleft() #往左边添加一个元素
douqueue.pop() #获取最右边的一个元素，并在队列中删除
douqueue.popleft() #获取最左边的一个元素
douqueue[0] #获取队列中最左边的第一个元素
douqueue[-1] #获取队列中最右边的第一个元素
#deque的这些操作足够我们去模拟栈和队列了
当然在实现栈时我们通过Python内置的list来进行实现的，在末尾插入和删除一个元素所使用的时间都是
O(1)的，符合stack的要求，所以在实际的应用中完全可以将list当做栈来使用
class Stack(object):
def __init__(self): #初始化将列表看为堆栈
self.stack = []
def push(self,value): #进栈
self.stack.append(value)
def pop(self): #出栈
if self.stack:
self.stack.pop()
else:
raise LookupError('stack is empty');
def is_empty(self): #栈为空的情况
return bool(self.stack)
def top(self):
return self.stack[-1] #取出目前stack中最新的元素
最后还想使用链表来实现一个最基本的队列，定义一个头结点，左边指向队列的开头，右边指向队列的
末尾，这样插入元素和取出元素时都是一个O(1)的操作
class Head(object): #头结点
def __init__(self):
self.left = None #左边指向队列的开头节点
self.right = None #右边指向队列的结尾节点
class Node(object): #中间节点
def __init__(self,value):
self.value = value
self.next = None
class Queue(object):
def __init__(self):
self.head = Head() #初始化节点
def enqueue(self,value):
newnode = Node(value)
if self.head.right: #队列中元素不为空的情况
self.head.next,self.head.right=newnode,newnode
else:
self.head.right,self.head.left = newnode,newnode
def dequeue(self): #出队
if self.head.left and (self.head.left == self.head.right): #队列中有且仅有一个元素了
temp = self.head.left.value
self.head.right,self.head.left = None,None
return temp
elif self.head.left and (self.head.left != self.head.right): #队列中不止一个元素
temp=self.head.left.value
self.head.left = self.head.left.next
return temp
else: #队列为空
raise LookupError("queue is empty")
def is_empty(self):
return (True if self.head.left else False)
def top(self):
if self.head.left:
return self.head.left.value
else:
raise LookupError("queue is empty")
四、Map
1.Java中的Map
(1)HashMap
HashMap实现了Map接口，允许放入key为null的元素，也允许插入value为null的元素，该容器不保证元
素的顺序，根据需要可能会对元素进行重新哈希，元素的顺序也会被重新打散，在不同的时间迭代同一个
HashMap的顺序可能会不同，HashMap还尚未实现同步
根据对冲突的处理方式，哈希表有两种实现方式，一种是开放地址方式，一种是冲突链表方式，Java
中的HashMap采用的是冲突链表方式
从这张图中可以看出初始容量（inital capacity）和负载系数（load factor）这两个参数影响了HashMap的
性能，当entry的数量超过了capacity*load_factor时，容器会自动进行扩容并重新哈希。对于插入元素比较多的
场景，将初始容量设大可以减少重新哈希的次数
将对象放入到HashMap时，有两个方法特别重要，hashCode()方法决定了对象会被放入到哪个bucket
中，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是同一个对象。当需要将自定义的对象
放入HashMap时需要重写hashCode()方法和equals() 方法
get（Object key）方法根据指定的key值返回对应的value，该方法调用了getEnery(Object key)得到
相应的entry，然后返回entry.getValue()；算法的思想首先是通过哈希函数得到对应bucket的下标，然后
一次遍历冲突链表，通过key.equals(k)方法来判断是否是要寻找的那个entry
//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){ //得到冲突的链表，依次进行遍历
Object k;
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
public 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);
}
//在冲突链表头部插入新的Index
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash,key,value,e);
size++;
}
remove(Object key)方法删除Key值对应的entry，核心算法在removeEntryForKey(Object key)实现的
removeEntryForKey(Object key)方法首先会找到key值对应的entry，然后再删除该entry
final Entry<K,V> removeEntryForKey(Object key){
int hash = (key!=null)? hash(key):0;
int index = hash&(table.length - 1);
Entry<K,V> prev = table[index]; //冲突的链表
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;
}
(2) TreeMap
Java中的TreeMap会按照key的大小顺序进行排序，key的大小比较可以通过其本身的自然顺序，也可以
通过构造时传入的比较器；TreeMap底层通过红黑树来实现，其containskey()、get()、put()和remove()都
有着log(n)的时间复杂度，TreeMap是非同步的
先简单的介绍下红黑树吧，红黑树可以说是二叉搜索树的改良版，目的就是解决后者退化成单链表后搜索
的时间复杂度由O（N）变成O（logN）的问题，它是一种近似的二叉查找树，能够确保任何一个节点的左右子
树的高度差不会超过二者中较低那个的一倍
具体来看，红黑树的特点如下：
- 每个节点只能是红色或者黑色的
- 根节点必须是黑色的
- 红色节点的孩子和父亲都不能是红色
- 对于每个节点，从该点至叶子节点的任何路径都含有相同颜色的黑色节点
在树的结构发生改变时（插入或者删除操作），会破坏上述要求，需要经过调整才能使得树重新满足
约束的条件，调整一方面是颜色调整，另一方面是结构的调整，结构调整包括左旋和右旋，下面对一些
常见的操作写出代码
左旋的过程是将x的右子树绕逆时针旋转，使得x的右子树成为x的父节点
//Rotate Left左旋函数代码 以上图所示为例进行说明
private void rotateLeft(Entry<K,V> p){
if(p!=null){
Entry<K,V> r = p.right; //假设p节点为x节点，也即是待旋转的节点，r节点就是y节点
if(r.left!=null) //修改y节点左节点的引用关系
p.right = r.left; //将y节点的左节点(B子树)改为x的右节点
r.left.parent = p; //将y节点的左节点(B子树)的父节点设置成为x节点
//修改y节点与x节点父节点的引用关系
r.parent = p.parent; //将原来x节点的父节点修改成y节点的父节点
//判断x是其父节点的左节点还是右节点
if(p.parent ==null) //p节点是根节点的情况
root = r;
else if(p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//修改x节点和y节点间的应用关系
r.left = p;
p.parent = r;
}
}
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父节点
//右旋的过程代码 Rotate Right 原理与左旋过程相似
private void rotateRight(Entry<K,V> p){
if(p!=null){
Entry<K,V> l = p.left;
if(l.right !=null)
p.left = l.right;
l.rigth.parent = p;
l.parent = p.parent;
if(p.parent == null)
root = l;
else if(p.parent.left == p)
p.parent.left = l;
else
p.parent.right = l;
l.right = p;
p.parent = l;
}
}
寻找节点后继，对于一颗二叉查找树，其后继（树中比大于t的最小的那个元素），一般可以通过下面的
方法来找到：t的右子树不空，则t的后继结点是其右子树中最小的那个元素；t的右孩子为空，则t的后继是其
第一个向走的祖先
//寻找节点后继函数successor()
public static TreeMap.Entry<K,V> successor(Entry<K,V> t){
if(t==null)
return null;
else if(t.right !=null){ //t的右子树不为空，则t的后继是其右子树中最小的那个元素
Entry<K,V> p =t.right;
while(p.left !=null)
p=p.left;
return p;
}else{ //t的右孩子为空,则t的后继是其第一个向左走的祖先
Entry<K,V> p = t.parent; //获取当前节点的父节点
Entry<K,v> ch = t ; //当前节点
while(p!=null && ch == p.right){ //当前节点是其父节点的右节点
ch = p;
p = p.parent;
}
return p;
}
}
get（object key）：根据指定的key值返回指定的value值，getEntry（）是算法的核心，根据key的自然
顺序或者比较器的顺序对二叉查找树进行查找
//核心算法代码
final Entry<K,V> getEntry(Object key){
if(key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
//使用元素的自然顺序
Entry<K,V> p = root;
while(p!=null){
int cmp = k.compareTo(p.key);
if(cmp<0) //向左找
p = p.left;
else if (cmp>0) //向右找
p = p.right;
else
return p;
}
return null
}
put(K key , V value) 方法是将key,value对添加到map里面，该方法在执行时会先对map做一次检查，看
是否包含该元祖，如果已经包含则直接返回，如果没有找到则会红黑树中插入新的Entry，插入时首先在红黑
树上找到合适的位置，然后创建一个新的Entry并插入，新插入的节点一定是树的叶子，在插入完成后还需要进
行调整，比如旋转或者改变某些节点的颜色
remove（Object key）的作用是删除key值对应的Entry，该方法首先通过getEntry(Object key)方法找到
key值对应的entry，然后调用deleteentry删除对应的entry；删除之后需要对红黑树进行调整。由于红黑树是
一颗增强版的二叉查找树，删除操作非常相似，普通的二叉查找树有两种情况，一是删除点p的左右子树都
为空（直接删除即可），或有一颗子树为空（只有一颗子树非空）、二是左右子树均不为空，这时可以使用
p的后继节点来代替p，然后使用情况一来删除s，此时s节点一定满足情况一
在具体的调整函数中，只有删除点BLACK的时候，才会触发调整函数，删除RED节点不会破坏红
黑树的任何性质，删除BLACK点会破坏规则4
(3)LinkedHashMap
从名字上就可以看出该容器是linked list 和HashMap的混合体，它同时满足二者的某些特性。具体来说
LinkedHashMap是HashMap的直接子类，前者在后者的基础上采用双向链表的形式将所有entry连接起来，
这样做可以使元素的迭代顺序跟插入顺序相同；此外，迭代LinkedHashMap时不需要像HashMap那样遍历整
个Table，而只需要遍历header指向的双向链表即可，LinkedHashMap的迭代时间就只跟entry的个数有关，与
Table的大小无关
get（Object key）方法即为根据key值返回对应的value值，原理和HashMap相同
put（K key，V key）方法将指定的key，value对添加到map中，但是这里的插入有两重含义，一是从
table的角度来看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法，将新的entry插
入到冲突链表的头部；二是从header的角度来看，新的entry需要插入到双向链表的尾部
remove（Object key）的作用就是删除key值对应entry，具体实现方法为removeEntryForKey（Object key）
实现的过程就是先找到key对应的entry在进行删除；删除时既要在hashtable的bucket中删除，也要从双向链表
中删除
final Entry<K,V> removeEntryForKey(Object key){
int hash = (key == null)? 0:hash(key);
int index = hash&(table.length-1);
Entry<K,V> prev = table[index]; //得到冲突链表
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
size--;
// 1. 将e从对应bucket的冲突链表中删除
if (prev == e) table[i] = next;
else prev.next = next;
// 2. 将e从双向链表中删除
e.before.after = e.after;
e.after.before = e.before;
return e;
}
prev = e; e = next;
}
return e;
使用LinkedHashMap实现缓存
LinkedHashMap可以很方便地实现一个FIFO替换策略的缓存，LinkedHashMap有一个子类方法可以告
诉Map是否要删除“最老”的Entry，所谓最老就是当前的Map中最早插入的Entry，如果方法返回true则最老
的那个元素删除。每次插入新元素时，LinkedHashMap会自动询问那个子类方法是否删除，当元素个数超
过一定数量时让那个子类方法返回true即可实现一个固定大小的FIFO策略的缓存
//一个固定大小的FIFO替换策略的缓存实现
class FIFOCache<K,V> extends LinkedHashMap<K,V>{
private final int cacheSize;
public FIFOCache(int cacheSize){
this.cacheSize = cacheSize;
}
//当Entry个数超过cacheSize时，删除最老的Entry
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
return size() > cacheSize;
}
}
五、Set集合
1.Java中的Set
在Java中，TreeSet和TreeMap、HashMap和HashSet、LinkedHashMap和LinkedHashSet都具有
相同的实现，前者仅仅是对后者做了一层包装
2.Python中的Set
集合是Python中一个最基本的数据类型，在Cpython中，集合被实现为带有空值的字典，只有健才是实际的
集合元素，所以集合的底层是用哈希来实现的，它最大的特点就是其中的元素是唯一的，无序的。在元素顺序的
重要性不如元素的唯一性和测试元素是否包含在集合中的效率时，set是最好的选择
在pydu模块中，set.OrderedSet（iterable = None）可以保持插入元素有序的集合
Python中对于Set去重的底层实现原理： set的去重是通过两个函数 hash和eq结合实现的，当两个变量的
的哈希值不相同时，就认为这两个变量是不同的，当哈希值一样，而调用eq（）方法时，返回值为true认为这
两个变量是同一个，应该去除一个，返回False时，不去重
六、优先队列
1.Java中的优先队列
PriorityQueue是一种的特殊的队列，即优先队列，优先队列的作用是保证每次取出的元素都是队列中权
值最小的或者权值最大的；优先队列又称为堆，堆又分为小顶堆和大顶堆，小顶堆即是每一个根节点都会小
其左孩子和右孩子，而大顶堆即是每一个根节点都会大于其左孩子和右孩子
Java中的优先队列即为PriorityQueue，它是通过完全二叉树来实现的小顶堆，底层是通过数组来进行存
储数据的，不允许放入null。元素大小的评判可以通过元素本身的自然顺序，也可以通过构造时传入的比较器；
从上面的这张图中可以看出，每个元素按照层序遍历的方式进行编号后，父子节点的编号之间存在
如下关系，所以使用来进行存储是非常方便的
leftNo = parentNo * 2+1
rightNo = parentNo*2 + 2
parentNo = (nodeNo-1)/2
PriorityQueue的peek（）和element（）的时间复杂度都是O(1)的，而add（）、offer（）、无参数
的remove（）以及poll（）方法的时间复杂度都是log(N)
add（）方法和offer（）方法都是向优先队列中插入元素，只不过前者插入失败后抛出异常，后者返回
false，二者的底层实现原理相同；插入元素破坏小顶堆的性质，需要进行调整，具体的调整的过程为从k指
定的位置开始，将x逐层与当前点的parent进行比较并交换，知道满足x>=queue[parent]
//offer(E e) 函数源码
public boolean offer(E e){
if(e == null) //不允许放入null元素
throw new NullPointerException();
...
int i = size;
if(i>=queue.length)
grow(i+1); //自动扩容 就是申请一个更大的数组，将原数组的元素复制过去
size +=1;
if(i==0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i,e); //调整函数
return true;
}
//siftUp()函数 该方法用于插入元素x并维持堆的特性
private void siftUp(int k,E x){
while(k>0){
int parent = (k-1) >> 1; //根据子节点求父节点下标
Object e = queue[parent];
if(comparator.compare(x,(E) e)>=0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
element （）和 peek（）都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者区别
就是前者方法失败时抛出异常，后者返回null。根据小顶堆的性质，堆顶的那个元素就是最小的
//peak() 函数源码
public E peek(){
if(size == 0)
return null
return (E) queue[0]; //0下标就是最小的那个
}
remove（）和poll（）方法都是获取并删除队首元素，区别是当方法失败时，前者抛出异常，后者返回
null，删除操作会改变队列的结构，为维护小顶堆的性质，需要进行调整，siftDown()方法是从k指定的位置
开始，将x逐层向下与当前点的左右孩子中较小的那个进行交换，直到x小于或等于左右孩子中的任何一个为止
public E poll(){
if(size == 0)
return null
int s = --size;
...
E result = (E) queue[0]; //0下标处的元素是最小的那个元素
E x = (E) queue[s]; //原队列中的最后一个元素
queue[s] = null; //使用最后一个元素替换0下标位置的元素
if(s!=0)
siftDown(0,x); //使用siftDown()方法对堆进行调整
return result;
}
//siftDown()方法源码
private void siftDown(int k,E x){
int half = size>>1;
while(k<half){
//首先找到左右孩子中较小的那个，记录到c中，并用child记录其下标
int child = (k<<1)+1; //child表示左节点
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right]; //左节点的值大于右节点的值
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
remove(Object o)方法用于删除队列中跟o相等的某一个元素，删除操作会改变队列的结构，需要进行调整，
具体可分为两种情况，删除的是最后一个元素，直接删即可，不需要进行调整；当删除的不是最后一个元素时
从删除点开始以最后一个元素为参照调用一次siftDown()函数即可
//remove(Object o)
public boolean remove(Object o){
//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
int index = indexof(o); //假设o存在于该队列中
if (index == -1)
return false; //实际上不存在
int s = --size; //s为删除的最后一个元素的下标
if(s == i) //待删除的元素为最后一个元素
queue[i] = null
else{
E moved = (E) queue[s];
queue[s] = null;
siftDown(i,moved); //如果不是最后一个元素，找到最后一个元素调用siftDown()方法
}
return true;
}
2.Python中的优先队列
Python中提供了heapq模块，可以让我们很方便地堆的相关操作进行简化，常用的方法如下：
- heappush（heap，item）往堆中插入一条新的值
- heappop（heap）从堆中弹出最小值
- heapreplace（heap，item）从堆中弹出最小值，并向堆中插入item
heapify（x） 以线性时间将列表转化成一个堆
#有关堆的操作函数 import heapq #第一种创建堆的方法 nums = [2,1,7,53,32,44,89,4] heap = [] for num in nums: heapq.heappush(heap,num) #将原列表中的元素加入堆 print(heap[0]) #查看堆首的元素，底层是一个列表 print(heap) heapq.heapreplace(heap,13) #删除队首的元素并添加一个新的元素 print(heap) #第二种创建堆的方法 nums2 = [5,6,7,8,3,3,53,89] heapq.heapify(nums2) #将一个列表初始化成一个堆 print([heapq.heappop(nums2) for _ in range(len(nums2))]) #一行代码实现堆排序，时间复杂度为O（nlogn） #如何去建立一个大根堆 #如何建立一个大根堆 a = [] for i in [4,5,2,2,55,64,2,255,6]: heapq.heappush(a,-i) print(list(map(lambda x:-x,a))) #heapq里面没有直接提供建立大根堆的方法,在每次push时给元素加一个负号，此时最小值就变成最大值了 #实际上的最大值就处于堆顶了，返回时在取负即可