Java 集合框架
- 接口:是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口,是为了以不同的方式操作集合对象
- 实现(类):是集合接口的具体实现。从本质上讲,它们是可重复使用的数据结构,例如:ArrayList、LinkedList、HashSet、HashMap。
- 算法:是实现集合接口的对象里的方法执行的一些有用的计算,例如:搜索和排序。这些算法被称为多态,那是因为相同的方法可以在相似的接口上有着不同的实现。
一、Set和List的区别:
- Set 接口实例存储的是无序的,不重复的数据。List 接口实例存储的是有序的,可以重复的元素
- Set检索效率低下,删除和插入效率高,插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>
- List和数组类似,可以动态增长,根据实际存储的数据的长度自动增长List的长度。查找元素效率高,插入删除效率低,因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector>
二、如何使用迭代器:
遍历 ArrayList
1 | import java.util.*; |
遍历 Map
1 | import java.util.*; |
三、ArrayList
ArrayList类是一个可以动态修改的副本,与普通副本的区别就是它是没有固定大小的限制,我们可以添加或删除元素。
1、基本实现
1 | import java.util.ArrayList; |
2、常用方法
方法 | 描述 |
---|---|
add() | 将元素插入到指定位置的 arraylist 中 |
get() | 通过索引值获取 arraylist 中的元素 |
remove() | 删除 arraylist 里的单个元素 |
size() | 返回 arraylist 里元素数量 |
set() | 替换 arraylist 中指定索引的元素 |
toString() | 将 arraylist 转换为字符串 |
四、LinkedList
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。
链表可分为单向链表和双向链表。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。
一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。
Java LinkedList(链表) 类似于 ArrayList,是一种常用的数据容器。
与 ArrayList 相比,LinkedList 的增加和删除对操作效率更高,而查找和修改的操作效率较低。
以下情况使用 ArrayList :
- 频繁访问列表中的某一个元素。
- 只需要在列表末尾进行添加和删除元素操作。
以下情况使用 LinkedList :
- 你需要通过循环迭代来访问列表中的某些元素。
- 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。
1、创建一个简单的链表实例
1 | import java.util.LinkedList; |
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 | // 引入 HashMap 类 |
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相同,不代表两个对象就相同,只能说明这两个对象在散列存储结构中,存放于同一个位置