Java集合框架类
java集合框架类图
Collection接口(List、Set、Queue、Stack):
Map接口:
Collection集合
1、List
ArrayList(数组)
(1) 增加
1、末尾插入
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
2、指定位置插入
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
结论:指定位置插入需要移动大量元素的位置,所以效率不高。
(2) 修改
public E set(int index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
结论:只能修改已经存在的对象。
(3) 删除
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
结论:删除也会移动大量的元素。效率不高
(4) 遍历
List<String> strList = new ArrayList<String>();
strList.add(“123”);
for(String str :strList){
System.out.println(str);
}
总结:为了提高效率。最好为ArrayList的大小赋个初值。
LinkedList(双向链表)
(1) 增加
1、public boolean add(E e) {
addBefore(e, header);
return true;
}
private Entry<E> addBefore(E e, Entry<E> entry) {
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
modCount++;
return newEntry;
}
2、 public void addFirst(E e) {
addBefore(e, header.next);
}
public void addLast(E e) {
addBefore(e, header);
}
3、指定位置添加数据
public void add(int index, E element) {
addBefore(element, (index==size ? header : entry(index)));
}
结论:正常Add(E e)方法就是在链表尾部添加节点。指定位置添加数据不需要移动大量数据。
只需改变带插入位置前后节点的指针即可。
(2) 删除
public E remove(int index) {
return remove(entry(index));
}
/**
* Returns the indexed entry.
*/
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
结论:从前向后遍历删除数据。删除和添加数据时候。不需要移动大量数据。只需遍历,
所以相对于ArrayList效率较高。
(3) 修改
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
结论:修改相应节点的值
(4) 遍历
略。
2、Set
HashSet(底层由HashMap实现)
public HashSet() {
map = new HashMap<E,Object>();
}
HashSet实现是利用HashMap的Key存储值。Value都是Object。
(1) 增加
参考HashMap实现。
(2) 删除
参考HashMap实现。
(3) 修改
参考HashMap实现。
(4) 遍历
参考HashMap实现。
TreeSet(底层由TreeMap实现)
public TreeSet() {
this(new TreeMap<E,Object>());
}
TreeSet实现是利用TreeMap的Key存储值。Value都是Object。
(1) 增加
参考TreeMap实现。
(2) 删除
参考TreeMap实现。
(3) 修改
参考TreeMap实现。
(4) 遍历
参考TreeMap实现。
LinkedHashSet(底层由LinkedHashMap实现)
(1) 增加
参考LinkedHashMap实现。
(2) 删除
参考LinkedHashMap实现。
(3) 修改
参考LinkedHashMap实现。
(4) 遍历
参考LinkedHashMap实现。
3、Queue(先进先出)
底层数据结构是堆。
4、Stack(后进先出)
底层有数组实现。
(1) public synchronized E pop()
弹出栈顶元素,并删除栈顶元素。
(2) public synchronized E peek()
只弹出栈顶元素,不删除。
Map集合
<Key,value>的映射。Key不能重复。Value可以重复。
每对<Key,Value>组成一个单元Entity对象。
将Entity做为一个对象进行存储。
1、HashMap
底层维护一个Entity[]。
(1)增加
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
结论:1允许key为Null,2根据key的hashcode值确定该Entity在数组中的位置。3若该位置存在Key得用newValue替换oldValue。否则插入链表头部
(2)删除、修改
根据key的hashCode值找到对应的Entity对象。进行修改和删除操作。
(3)遍历
/**
* 1、第一种遍历方法
*/
Set<String> keys = hashMap.keySet();
for(String key : keys){
System.out.print("key: " + key);
System.out.print("value: " + hashMap.get(key));
System.out.println();
}
/**
* 2、第二种遍历方法
*/
Set<Map.Entry<String, String>> entrys1 = hashMap.entrySet();
for(Map.Entry<String, String> entry : entrys1){
System.out.print("key: " + entry.getKey());
System.out.print("value: " + entry.getValue());
System.out.println();
}
/**
* 3、第三种遍历方法(推荐)
*/
Set<Map.Entry<String, String>> entrys2 = hashMap.entrySet();
Iterator<Map.Entry<String, String>> iter = entrys2.iterator();
while(iter.hasNext()){
Map.Entry<String, String> entry = iter.next();
System.out.print("key: " + entry.getKey());
System.out.print("value: " + entry.getValue());
System.out.println();
}
2、TreeMap(按Key值的有序排列)
底层由一个红黑树结构构成。每个节点都是一个Entity对象。
(1) 增加
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
// TBD:
// 5045147: (coll) Adding null to an empty TreeSet should
// throw NullPointerException
//
// compare(key, key); // type check
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<K,V>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
结论:1、TreeMap支持自定义排序。可以设置实现Comparator接口的自定义排序类。
如果没有设置自定义排序规则。则按照key值升序排序。
2、插入数据会进行比较找到待插入的位置。
(2) 删除
删除一个树节点,也会重新调整树结构。所以效率不高。
(3) 修改
略。
(4) 遍历
参考HashMap的遍历
3、LinkedHashMap
继承自HashMap,底层的数据结构与HashMap相似。只不过HashMap是数组中存储单向链表,LinkedHashMap是数组中存储双向链表
LinkedHashMap保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的。
(1) 增加
略
(2) 删除
略
(3) 修改
略
(4) 遍历
略
4、IdentityHashMap
Map由 key-value组成,key用于检索value的内容。在正常情况下,可以不允许重复;重复在java中分为 2中情况,
一是内存地址重复,另一个是不同的地址但内容相等,而IdentityHashMap用于后者,即内容相等。
更详细的解释如下:在 IdentityHashMap 中,当且仅当 (k1==k2) 时,才认为两个键 k1 和 k2 相等(在正常 Map 实现(如 HashMap)中,当且仅当满足下列条件时才认为两个键 k1 和 k2 相等:(k1==null ? k2==null : e1.equals(e2)))。
此类不是 通用 Map 实现!此类实现 Map 接口时,它有意违反 Map 的常规协定,该协定在比较对象时强制使用 equals 方法。此类设计仅用于其中需要引用相等性语义的罕见情况
5、ConcurrentHashMap
concurrenthashmap是一个非常好的map实现,在高并发操作的场景下会有非常好的效率。实现的目的主要是为了避免同步操作时对整个map对象进行锁定从而提高并发访问能力。
ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修 改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分,每个段其实就是一个小的hash table,它们有自己的锁。只要多个修改操作发生在不同的段上,它们就可以并发进行。
ConcurrentHashMap完全允许多个读操作并发进行,读操作并不需要加锁。如果使用传统的技术,如HashMap中的实现,如果允许可 以在hash链的中间添加或删除元素,读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可 变的。HashEntry代表每个hash链中的一个节点,其结构如下所示:
Java代码
- static final class HashEntry<K,V> {
- final K key;
- final int hash;
- volatile V value;
- final HashEntry<K,V> next;
- }
可以看到除了value不是final的,其它值都是final的,这意味着不能从hash链的中间或尾部添加或删除节点,因为这需要修改next 引用值,所有的节点的修改只能从头部开始。对于put操作,可以一律添加到Hash链的头部。但是对于remove操作,可能需要从中间删除一个节点,这就需要将要删除节点的前面所有节点整个复制一遍,最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值,将value设置成volatile,这避免了加锁
Iterable接口和Comparator、Comparable接口
1、Iterable接口
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
集合中增强for循环。实际是利用Iterable接口。实现Iterable接口的集合或对象可以使用增强for循环。
2、Comparator、Comparable接口
实现Comparator、Comparable接口的类。可以自定义排序。
集合常用工具类
1、Collections
1)集合的排序
2)集合的二分查找。
3)集合的拷贝
4)集合的反转和旋转。
2、Arrays
Arrays.asList(数组对象) 将Array转化为List类型对象。
用Collection接口中的toArray方法,将集合转化为数组。
1)数组的排序
2)数组的交换
3)数组的拷贝
4)数组的查找(二分查找等)
最新文章
- NopCommerce 增加 Customer Field
- webpack学习笔记
- swift UIImage加载远程图片和圆角矩形
- C# Ping的例子,可用于测试网络,延迟xx毫秒 C#编写网站测速
- bzoj1003: [ZJOI2006]物流运输
- Centos6.5 install Python2.7 &; django &; mysql &; apache
- MVC零基础学习整理(一)
- 解决Windows内存问题的两个小工具RamMap和VMMap(这个更牛更好)
- (CLR-Via-C#) 类型基础
- Spring Boot(一):入门篇+前端访问后端
- git知识总结-4.git服务器搭建及迁移git仓库
- ASP.NET 实现PDF文件下载[转]
- Ubuntu下修改CMake版本
- 通过js去掉所有的html标签,得到HTML标签中的所有内容
- zw版【转发&#183;台湾nvp系列Delphi例程】HALCON TestRegionPoint2
- gmake与make的区别
- linux的定制和发布(二)
- ICPCCamp 2017 I Coprime Queries
- 【BZOJ1493】【NOI2007】项链工厂(线段树)
- JQuery Ajax 使用FormData上传文件对象