Java 集合框架

img

  • 接口:是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口,是为了以不同的方式操作集合对象
  • 实现(类):是集合接口的具体实现。从本质上讲,它们是可重复使用的数据结构,例如:ArrayList、LinkedList、HashSet、HashMap。
  • 算法:是实现集合接口的对象里的方法执行的一些有用的计算,例如:搜索和排序。这些算法被称为多态,那是因为相同的方法可以在相似的接口上有着不同的实现。

一、Set和List的区别:

  • Set 接口实例存储的是无序的,不重复的数据。List 接口实例存储的是有序的,可以重复的元素
  • Set检索效率低下,删除和插入效率高,插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>
  • List和数组类似,可以动态增长,根据实际存储的数据的长度自动增长List的长度。查找元素效率高,插入删除效率低,因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector>

二、如何使用迭代器:

遍历 ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

public class Test{
public static void main(String[] args) {
List<String> list=new ArrayList<String>();
list.add("Hello");
list.add("World");
list.add("HAHAHAHA");
//第一种遍历方法使用 For-Each 遍历 List
for (String str : list) { //也可以改写 for(int i=0;i<list.size();i++) 这种形式
System.out.println(str);
}

//第二种遍历,把链表变为数组相关的内容进行遍历
String[] strArray=new String[list.size()];
list.toArray(strArray);
for(int i=0;i<strArray.length;i++) //这里也可以改写为 for(String str:strArray) 这种形式
{
System.out.println(strArray[i]);
}

//第三种遍历 使用迭代器进行相关遍历,该方法可以不用担心在遍历的过程中会超出集合的长度。

Iterator<String> ite=list.iterator();
while(ite.hasNext())//判断下一个元素之后有值
{
System.out.println(ite.next());
}
}
}
遍历 Map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

public class Test{
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");

//第一种:普遍使用,二次取值
System.out.println("通过Map.keySet遍历key和value:");
for (String key : map.keySet()) {
System.out.println("key= "+ key + " and value= " + map.get(key));
}

//第二种
System.out.println("通过Map.entrySet使用iterator遍历key和value:");
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

//第三种:推荐,尤其是容量大时
System.out.println("通过Map.entrySet遍历key和value");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}

//第四种
System.out.println("通过Map.values()遍历所有的value,但不能遍历key");
for (String v : map.values()) {
System.out.println("value= " + v);
}
}
}

三、ArrayList

ArrayList类是一个可以动态修改的副本,与普通副本的区别就是它是没有固定大小的限制,我们可以添加或删除元素。

1、基本实现
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.ArrayList;

public class RunoobTest {
public static void main(String[] args) {
ArrayList<String> sites = new ArrayList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites);
}
}
2、常用方法
方法 描述
add() 将元素插入到指定位置的 arraylist 中
get() 通过索引值获取 arraylist 中的元素
remove() 删除 arraylist 里的单个元素
size() 返回 arraylist 里元素数量
set() 替换 arraylist 中指定索引的元素
toString() 将 arraylist 转换为字符串

四、LinkedList

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。

链表可分为单向链表和双向链表。

一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

img

一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

img

Java LinkedList(链表) 类似于 ArrayList,是一种常用的数据容器。

与 ArrayList 相比,LinkedList 的增加和删除对操作效率更高,而查找和修改的操作效率较低。

以下情况使用 ArrayList :

  • 频繁访问列表中的某一个元素。
  • 只需要在列表末尾进行添加和删除元素操作。

以下情况使用 LinkedList :

  • 你需要通过循环迭代来访问列表中的某些元素。
  • 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。
1、创建一个简单的链表实例
1
2
3
4
5
6
7
8
9
10
11
12
import java.util.LinkedList;

public class RunoobTest {
public static void main(String[] args) {
LinkedList<String> sites = new LinkedList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites);
}
}
2、常用方法
方法 描述
public int size() 返回链表元素个数。
public E set(int index, E element) 设置指定位置的元素。
public Object clone() 克隆该列表。
public boolean add(E e) 链表末尾添加元素,返回是否成功,成功为 true,失败为 false。
public void add(int index, E element) 向指定位置插入元素。
public void addFirst(E e) 元素添加到头部
public boolean offer(E e) 向链表末尾添加元素,返回是否成功,成功为 true,失败为 false。
public void clear() 清空链表。
public boolean remove(Object o) 删除某一元素,返回是否成功,成功为 true,失败为 false。
public E remove(int index) 删除指定位置的元素。
public E remove() 删除并返回第一个元素。
public E get(int index) 返回指定位置的元素。

五、HashMap

1、基本内容:

HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口,根据键的 HashCode 值存储数据,具有很快的访问速度,最多允许一条记录的键为 null,不支持线程同步。

HashMap 是无序的,即不会记录插入的顺序。

HashMap 继承于AbstractMap,实现了 Map、Cloneable、java.io.Serializable 接口。

2、HashMap 的 key 与 value 类型可以相同也可以不同,可以是字符串(String)类型的 key 和 value,也可以是整型(Integer)的 key 和字符串(String)类型的 value。
3、HashMap 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类。
基本类型 引用类型
boolean Boolean
byte Byte
short Short
int Integer
long Long
float Float
double Double
char Character
4、例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 引入 HashMap 类      
import java.util.HashMap;

public class RunoobTest {
public static void main(String[] args) {
// 创建 HashMap 对象 Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// 添加键值对
Sites.put(1, "Google");
Sites.put(2, "Runoob");
Sites.put(3, "Taobao");
Sites.put(4, "Zhihu");
System.out.println(Sites);
}
}
//输出结果:{1=Google, 2=Runoob, 3=Taobao, 4=Zhihu}
5、常用方法:
方法 描述
clear() 删除 hashMap 中的所有键/值对
clone() 复制一份 hashMap
isEmpty() 判断 hashMap 是否为空
size() 计算 hashMap 中键/值对的数量
put() 将键/值对添加到 hashMap 中
remove() 删除 hashMap 中指定键 key 的映射关系
replace() 替换 hashMap 中是指定的 key 对应的 value。
get() 获取指定 key 对应对 value
entrySet() 返回 hashMap 中所有映射项的集合集合视图。
keySet() 返回 hashMap 中所有 key 组成的集合视图。
values() 返回 hashMap 中存在的所有 value 值。

参考文章

六、Hashcode方法与equals方法

(一)、hashcode是什么?
1、hash和hash表是什么

hash是一个函数,该函数中的实现就是一种算法,就是通过一系列的算法来得到一个hash值。这个时候,我们就需要知道另一个东西,hash表,通过hash算法得到的hash值就在这张hash表中,也就是说,hash表就是所有的hash值组成的,有很多种hash函数,也就代表着有很多种算法得到hash值

2、hashcode

hashcode就是通过hash函数得来的,通俗的说,就是通过某一种算法得到的,hashcode就是在hash表中有对应的位置。

每个对象都有hashcode,对象的hashcode怎么得来的呢?

首先一个对象肯定有物理地址,对象的物理地址跟这个hashcode地址不一样,hashcode代表对象的地址说的是对象在hash表中的位置,物理地址说的对象存放在内存中的地址

通过对象的内部地址(也就是物理地址)转换成一个整数,然后该整数通过hash函数的算法就得到了hashcode。所以,hashcode就是在hash表中对应的位置。

举个例子,hash表中有 hashcode为1、hashcode为2、(…)3、4、5、6、7、8这样八个位置,有一个对象A,A的物理地址转换为一个整数17(这是假如),就通过直接取余算法,17%8=1,那么A的hashcode就为1,且A就在hash表中1的位置。

(二)、hashcode有什么作用

HashCode的存在主要是为了查找的快捷性,HashCode是用来在散列存储结构中确定对象的存储地址的(后半句说的用hashcode来代表对象就是在hash表中的位置)

比如:我们有一个能存放1000个数这样大的内存中,在其中要存放1000个不一样的数字,用最笨的方法,就是存一个数字,就遍历一遍,看有没有相同得数,当存了900个数字,开始存901个数字的时候,就需要跟900个数字进行对比,这样就很麻烦,很是消耗时间,用hashcode来记录对象的位置,来看一下。

hash表中有1、2、3、4、5、6、7、8个位置,存第一个数,hashcode为1,该数就放在hash表中1的位置,存到100个数字,hash表中8个位置会有很多数字了,1中可能有20个数字,存101个数字时,他先查hashcode值对应的位置,假设为1,那么就有20个数字和他的hashcode相同,他只需要跟这20个数字相比较(equals),如果每一个相同,那么就放在1这个位置,这样比较的次数就少了很多,实际上hash表中有很多位置,这里只是举例只有8个,实际上,如果hash表很大,那么比较的次数就很少很少了。

!!!值如果相等那么hashcode一定相等,所以先比较hashcode再用equals方法比较

(三)、equals方法和hashcode的关系

通过前面这个例子,大概可以知道,先通过hashcode来比较,如果hashcode相等,那么就用equals方法来比较两个对象是否相等。

用个例子说明:上面说的hash表中的8个位置,就好比8个桶,每个桶里能装很多的对象,对象A通过hash函数算法得到将它放到1号桶中,当然肯定有别的对象也会放到1号桶中,如果对象B也通过算法分到了1号桶,那么它如何识别桶中其他对象是否和它一样呢,这时候就需要equals方法来进行筛选了。

1、如果两个对象equals相等,那么这两个对象的HashCode一定也相同

2、如果两个对象的HashCode相同,不代表两个对象就相同,只能说明这两个对象在散列存储结构中,存放于同一个位置