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(1234); //包装类的：自动装箱！ArrayList里面用的是一个Object对象数组，1234不是对象，理论上是不能存进去的，但是会自动转为Integer对象。 list.remove(new String("aaa")); System.out.println(list.size()); for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } list.set(3, new String("3333")); list.add(4, new String("3333")); 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(0);//返回的是Object类型 System.out.println(str); list.set(1, "ababa"); list.remove(0); } } class Dog { } System.arraycopy(elementData, index+1, 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==0; } public SxtArrayList(){ this(10); } public SxtArrayList(int initialCapacity){ if(initialCapacity<0){ 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*2+1]; System.arraycopy(elementData, 0, newArray, 0, elementData.length); for(int i=0;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 - 1; if (numMoved > 0){ System.arraycopy(elementData, index+1, elementData, index, numMoved);//原数组，原数组起点，目标数组，目标数组地点 } elementData[--size] = null; // Let gc do its work } public void remove(Object obj){ for(int i=0;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 + 1, size - index); elementData[index] = obj; size++; } private void ensureCapacity(){ //数组扩容和数据的拷贝 if(size==elementData.length){ Object[] newArray = new Object[size*2+1]; System.arraycopy(elementData, 0, newArray, 0, elementData.length);//原数组，被拷贝的起点索引。目标数组，拷贝到的起点索引，拷贝的长度。 for(int i=0;i<elementData.length;i++){ newArray[i] = elementData[i]; } elementData = newArray; } } private void rangeCheck(int index){ if(index<0||index>=size){ try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } } public static void main(String[] args) { SxtArrayList list = new SxtArrayList(3); list.add("333"); list.add("444"); list.add("5"); list.add("344433"); list.add("333"); list.add("333"); System.out.println(list.size()); // System.out.println(list.get(6)); list.remove("444"); 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<0||index>=size){ try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } } public Object get(int index){ //2 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=0;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(1,"BBBB"); list.add("ccc"); // list.remove(1); System.out.println(list.get(1)); } } //用来表示一个节点 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[990];//SxtEntry数组 int size; public void put(Object key,Object value){ SxtEntry e = new SxtEntry(key,value); //解决键值重复的处理 for(int i=0;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=0;i<size;i++){ if(arr[i].key.equals(key)){ return arr[i].value; } } return null; } public boolean containsKey(Object key){ for(int i=0;i<size;i++){ if(arr[i].key.equals(key)){ return true; } } return false; } public boolean containsValue(Object value){ for(int i=0;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[9]; //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=0;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=0;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 = 31; int result = 1; result = prime * result + ((id == null) ? 0 : id.hashCode()); result = prime * result + ((name == null) ? 0 : 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(243); Integer s2 = new Integer(243); 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(243)); } }
本文转自农夫山泉别墅博客园博客，原文链接：http://www.cnblogs.com/yaowen/p/4833552.html，如需转载请自行联系原作者
