map底层,数组加链表

集合:
是一个对象,只不过这个对象可以容纳别的对象。存放对象就是操作地址。
List:是有序可重复的。
Set:无顺序,不可重复,有重复则后面把前面的覆盖。
Map:键值对。 四大接口(Collection、Set、List、Map):
--Collection(集合)
--Set(没有顺序,不可重复)
--HashSet
--List(有顺序,重复)
--Map
--HashMap Collection为null表示容器都没有,Collection的方法:Collection为isEmpty()表示容器有,但是容器为空。Iterator<E> iterator()遍历容器,Object[] toArray()容器转换为数组,boolean add(E e)放入到容器,boolean remove(Object o)表示移除一个元素,但是这个元素还在,删除就是这个元素也没有了。boolean containsAll(Collection<?> c)有没有包含另一个容器里面所有的元素,boolean addAll(Collection<? extends E> c)把另一个容器的所有元素都包含进去, boolean removeAll(Collection<?> c)移除另一个容器中的所有元素,boolean retainAll(Collection<?> c)两个容器取交集,void clear()清除容器。 Set和List为Collection的子类,所以Set、List继承了Collection的所有方法。 List list = new ArrayList();
ArrayList数组列表,底层是private transient Object[] elementData(一个Object数组), public class Test01 {
@SuppressWarnings("unchecked")
public static void main(String[] args) {
List list = new ArrayList(); //ArrayList:底层实现时数组,线程不安全,效率高。所以,查询快(数组查询最快,挨个遍历)。修改、插入(插入一个后面也要移动)、删除(后面也要移动)慢。
//LinkedList:底层实现是链表,线程不安全,效率高。所以,查询慢(一个个的挨着向后找)。修改、插入(改变指针就可以了)、删除(改变指针就可以了)快。
//Vector:底层也是数组实现,线程安全的(多个线程共享的时候会有线程安全问题,但是定义成局部变量就跟线程没有关系),效率低。
list.add("aaa");
list.add("aaa");
list.add(new Date());
list.add(new Dog());
list.add(); //包装类的:自动装箱!ArrayList里面用的是一个Object对象数组,1234不是对象,理论上是不能存进去的,但是会自动转为Integer对象。
list.remove(new String("aaa"));
System.out.println(list.size());
for(int i=;i<list.size();i++){
System.out.println(list.get(i));
}
list.set(, new String(""));
list.add(, new String(""));
System.out.println(list.isEmpty());
list.remove(new Dog()); //hashcode和equals
System.out.println(list.size());
List list2 = new ArrayList();
list2.add("bbb");
list2.add("ccc");
list.add(list2);
//跟顺序的操作
String str = (String) list.get();//返回的是Object类型
System.out.println(str);
list.set(, "ababa");
list.remove();
}
}
class Dog {
} System.arraycopy(elementData, index+, elementData, index, numMoved);//原数组,原数组起点,目标数组,目标数组地点 list.remove(new String("aaa"));
list.remove("aaa");
new String("aaa")和"aaa"是2个不同的对象。 Dog a1 = new Dog();//cn.bjsxt.collection.Dog@123b25c
Dog a2 = new Dog();//cn.bjsxt.collection.Dog@2ba11b
System.out.println(a1 == a2);//false
System.out.println(a1.equals(a2));//false /**
* 自己实现一个ArrayList,帮助我们更好的理解ArrayList类的底层结构!
*
*/
public class SxtArrayList /*implements List*/ { private Object[] elementData;
private int size; public int size(){
return size;
} public boolean isEmpty(){
return size==;
} public SxtArrayList(){
this();
} public SxtArrayList(int initialCapacity){
if(initialCapacity<){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
elementData = new Object[initialCapacity];
} public void add(Object obj){
//数组扩容和数据的拷贝
if(size==elementData.length){
Object[] newArray = new Object[size*+];
System.arraycopy(elementData, , newArray, , elementData.length);
for(int i=;i<elementData.length;i++){
newArray[i] = elementData[i];
}
elementData = newArray;
} elementData[size++]=obj;
size++;
} public Object get(int index){
rangeCheck(index); return elementData[index];
} public void remove(int index){
rangeCheck(index);
//删除指定位置的对象
//a b d e
int numMoved = size - index - ;
if (numMoved > ){
System.arraycopy(elementData, index+, elementData, index,
numMoved);//原数组,原数组起点,目标数组,目标数组地点
}
elementData[--size] = null; // Let gc do its work
} public void remove(Object obj){
for(int i=;i<size;i++){
if(get(i).equals(obj)){ //注意:底层调用的equals方法而不是==.
remove(i);
}
}
} public Object set(int index,Object obj){
rangeCheck(index); Object oldValue = elementData[index];
elementData[index] = obj;
return oldValue;
} public void add(int index,Object obj){
rangeCheck(index); ensureCapacity(); //数组扩容 System.arraycopy(elementData, index, elementData, index + ,
size - index);
elementData[index] = obj;
size++;
} private void ensureCapacity(){
//数组扩容和数据的拷贝
if(size==elementData.length){
Object[] newArray = new Object[size*+];
System.arraycopy(elementData, , newArray, , elementData.length);//原数组,被拷贝的起点索引。目标数组,拷贝到的起点索引,拷贝的长度。
for(int i=;i<elementData.length;i++){
newArray[i] = elementData[i];
}
elementData = newArray;
}
} private void rangeCheck(int index){
if(index<||index>=size){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
} public static void main(String[] args) {
SxtArrayList list = new SxtArrayList();
list.add("");
list.add("");
list.add("");
list.add("");
list.add("");
list.add("");
System.out.println(list.size());
// System.out.println(list.get(6));
list.remove("");
System.out.println(list.size());
}
} //链表操作链表操作链表操作链表操作链表操作链表操作链表操作
//链表操作链表操作链表操作链表操作链表操作链表操作链表操作
import java.util.LinkedList;
//双向链表
public class SxtLinkedList /*implements List*/ {
private Node first;//由于是双向链表所以有首尾节点,而且只维护了首尾节点。
private Node last;
private int size;
public void add(Object obj){
Node n = new Node();
if(first==null){
n.setPrevious(null);
n.setObj(obj);
n.setNext(null);
first = n;
last = n;//赋值就是改变栈中变量的地址值的指向
}else{
//直接往last节点后增加新的节点
n.setPrevious(last);
n.setObj(obj);
n.setNext(null);
last.setNext(n);//堆中这个对象的里面的值改变
last = n;//改变栈中last的地址值的指向。
}
size++;
}
public int size(){
return size;
} private void rangeCheck(int index){
if(index<||index>=size){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
} public Object get(int index){ //
rangeCheck(index);
// 0 1 2 3 4
Node temp = node(index);
if(temp!=null){
return temp.obj;
}
return null;
} public Node node(int index){
Node temp = null;
if(first!=null){
temp = first;//temp指向第一个节点对象
for(int i=;i<index;i++){
temp = temp.next;//这里的赋值就是temp的地址值的指向依次向下移动。
}
}
LinkedList l;
return temp;
} public void remove(int index){
Node temp = node(index);
if(temp!=null){
Node up = temp.previous;//对象赋值就是传递地址
Node down = temp.next;
up.next = down;
down.previous = up;
size--;
}
} public void add(int index,Object obj){//数组列表的插入要做数组的copy,链表的插入直接打断连接。
Node temp = node(index);
Node newNode = new Node();
newNode.obj = obj;
if(temp!=null){
Node up = temp.previous;//对象的赋值赋的是地址的值,
//互相指向
up.next = newNode;
newNode.previous = up;
//互相指向
newNode.next = temp;
temp.previous = newNode;
size++;
}
} public static void main(String[] args) {
SxtLinkedList list = new SxtLinkedList();
list.add("aaa");
list.add("bbb");
list.add(,"BBBB");
list.add("ccc");
// list.remove(1);
System.out.println(list.get());
}
} //用来表示一个节点
public class Node {
Node previous; //上一个节点
Object obj;
Node next; //下一个节点 public Node() {
} public Node(Node previous, Object obj, Node next) {
super();
this.previous = previous;
this.obj = obj;
this.next = next;
} public Node getPrevious() {
return previous;
} public void setPrevious(Node previous) {
this.previous = previous;
} public Object getObj() {
return obj;
} public void setObj(Object obj) {
this.obj = obj;
} public Node getNext() {
return next;
} public void setNext(Node next) {
this.next = next;
}
}
//链表操作链表操作链表操作链表操作链表操作链表操作链表操作 Map
map中的key,value也是对象,key不能重复,Map中存的也是对象的地址。map.remove("高琪");表示只是把这个对象从容器中移除,这个对象并没有删除还在。
HashMap效率高线程不安全,HashTable效率低线程安全。 Map实现1:
/**
*自定义实现Map的功能!
*暂不完美!
*Map:存放键值对,根据键对象找对应的值对象.键不能重复!
*
*/
public class SxtMap001 {
SxtEntry[] arr = new SxtEntry[];//SxtEntry数组
int size;
public void put(Object key,Object value){
SxtEntry e = new SxtEntry(key,value);
//解决键值重复的处理
for(int i=;i<size;i++){
if(arr[i].key.equals(key)){
arr[i].value=value;
return ;
}
}
arr[size++] = e;
} public Object get(Object key){//每次查的时候都要遍历一次,所以效率低。
for(int i=;i<size;i++){
if(arr[i].key.equals(key)){
return arr[i].value;
}
}
return null;
} public boolean containsKey(Object key){
for(int i=;i<size;i++){
if(arr[i].key.equals(key)){
return true;
}
}
return false;
} public boolean containsValue(Object value){
for(int i=;i<size;i++){
if(arr[i].value.equals(value)){
return true;
}
}
return false;
} public static void main(String[] args) {
SxtMap001 m = new SxtMap001();
m.put("高琪", new Wife("杨幂"));
m.put("高琪", new Wife("李四"));
Wife w = (Wife) m.get("高琪");
System.out.println(w.name);
} } class SxtEntry {//定义一个类Entry(条目),里面是键值对。
Object key;
Object value; public SxtEntry(Object key, Object value) {
super();
this.key = key;
this.value = value;
}
} Map实现2,提高查询的效率。
对象的地址是根据哈希码生成的一个数。
Map的底层结构就是数组+链表(一个Map整体是一个数组,每个数组元素是一个链表,每个链表的节点是一个键值对的对象).
public class SxtMap002 {
//底层仍然是数组,每个数组元素是一个链表,链表的每个节点是key、value对。就是说一个数组元素里面,可以存多个值,取的时候遍历这个数组元素的链表。
LinkedList[] arr = new LinkedList[]; //Map的底层结构就是:数组+链表!
int size;
public void put(Object key,Object value){
SxtEntry e = new SxtEntry(key,value); int a = key.hashCode()%arr.length;
if(arr[a]==null){
LinkedList list = new LinkedList();
arr[a] = list;//数组的每个元素是链表,
list.add(e);//链表的每个节点是键值对。
}else{
LinkedList list = arr[a];
for(int i=;i<list.size();i++){
SxtEntry e2 = (SxtEntry) list.get(i);
if(e2.key.equals(key)){
e2.value = value; //键值重复直接覆盖!
return;
}
}
arr[a].add(e);
}
//a:1000-->1 b:10000-->13
} public Object get(Object key){
int a = key.hashCode()%arr.length;//获取这个对象的索引。
if(arr[a]!=null){//找到这个数组元素,且不为空。
LinkedList list = arr[a];
for(int i=;i<list.size();i++){//遍历这个链表(某一个数组元素)
SxtEntry e = (SxtEntry) list.get(i);
if(e.key.equals(key)){
return e.value;
}
}
}
return null;
} public static void main(String[] args) {
SxtMap002 m = new SxtMap002();
m.put("高琪", new Wife("杨幂"));
m.put("高琪", new Wife("李四"));
Wife w = (Wife) m.get("高琪");
System.out.println(w.name);
} } public class Wife {
public Wife(String string) {
}
} HashCode:
java中,两个内容相同的对象有相同的hashcodes,2个对象调用equals方法返回true则hashcodes一定相等。哈希算法可以快速定位这个对象存放的地方。
HashCode方法和equals要重写的话,这2个方法要一起重写,保证equals方法为true则hashcode一定相等。
=是判断2个对象是不是同一个对象,equals方法是判断2个对象的内容是不是相等。
Object类的equals方法是用=实现的,即比较对象的地址是不是相等。
string也重写了equals方法,即比较值是不是相等。 public class Student extends Object{
//类的equals、hashCode方法有一个重写则2个都要重写。
private Integer id;//Integer(包装类)的equals、hashCode重写了,即比较数值是不是相等。
private String name;//String的equals、hashCode方法重写了,比较字符串值。
private Date birthday;//Date类的equals、hashCode,比较毫秒数是不是相等。
//如果这2个方法不重写,默认hashCode是返回对象的地址,equals是比较地址(比较是不是同一个对象)
//重写后,这里根据id和name进行重写,如果是同一个对象则为true,如果id和name相等就是true
@Override
public int hashCode() {
final int prime = ;
int result = ;
result = prime * result + ((id == null) ? : id.hashCode());
result = prime * result + ((name == null) ? : name.hashCode());
return result;
}
//这里的equals是比较2个对象的id和name是不是一样的,一样则这2个对象相等(equals为true)。
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (id == null) {
if (other.id != null)
return false;
} else if (!id.equals(other.id))
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
} public class TestEquals { public static void main(String[] args) {
List list = new ArrayList();//List有顺序可重复
Integer s1 = new Integer();
Integer s2 = new Integer();
list.add(s1);
list.add(s2);
System.out.println(list.size()); Map map = new HashMap();
//键不能重复(判断键是不是重复了是通过equals方法)。
map.put(s1, "AAAA");
map.put(s2, "BBBBBB");
System.out.println(map.get());
} }

最新文章

  1. es6学习笔记
  2. 用C#缩小照片上传到各种空间
  3. Azure Redis Cache (3) 在Windows 环境下使用Redis Benchmark
  4. Android压力测试工具——Monkey
  5. Hadoop-2.7.3 问题收集
  6. 【转载】Linux下makefile详解--跟我一起写 Makefile
  7. URAL 1072 Routing(最短路)
  8. android 使用Activity做窗口弹出(模拟Dialog)
  9. MVC缓存,使用数据层缓存,添加或修改时让缓存失效
  10. wp8模拟器中使用电脑键盘和模拟器的版本解释
  11. JavaScript自动关闭窗口
  12. Day02_VI基本操作及C基础
  13. 基于drools创建自己的关系操作符
  14. Json部分知识(前台显示格式、Json-lib日期处理)
  15. python CSS
  16. C# 解决winform 窗体控件在窗体变化时闪烁的问题
  17. json.parseArray源码解析
  18. mysql安装运行(centos)
  19. python之进程和线程2
  20. ajax传输中文参数乱码,本地使用tomcat不乱码,liunx+weblogic乱码

热门文章

  1. easyui源码翻译1.32--Draggable(拖动)
  2. 8. Unity异常警告错误处理方法
  3. ANDROID_MARS学习笔记_S01原始版_022_MP3PLAYER002_本地及remote标签
  4. Type-C设计上的防护
  5. linux 匹配查询列表中包含某一特殊字符的所有行中的某一列
  6. Android Studio 快捷键 for Mac OS X 10.5+
  7. linux下查看防火墙当前状态,开启关闭等
  8. UVA 11426 GCD - Extreme (II) 欧拉函数
  9. asp.net的运行内幕
  10. 【UER #1】跳蚤OS(Trie)