`
uule
  • 浏览: 6348670 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

集合类总结

 
阅读更多

Collection   

├List   

│   ├LinkedList   

│   ├ArrayList   

│   └Vector   

│       └Stack   栈

└Set接口  

       └HashSet  (使用HashMap实现)

SortedSet接口

       └TreeSet   (使用TreeMap实现)

 

├Map   

    └Hashtable   

    └HashMap 

    └LinkedHashMap

    └WeakHashMap

├SortedMap

      └TreeMap  

 

 

public interface SortedSet<E> extends Set<E>
public interface SortedMap<K,V> extends Map<K,V> 

public class LinkedHashMap<K,V>  extends HashMap<K,V>   implements Map<K,V>

 TreeMap详细介绍(源码解析)和使用示例

 Java中HashMap和TreeMap的区别深入理解

 

 

问题1:HashMap与Hashtable的区别 

 

Hashtable是Dictionary类的子类,HashMap是Map接口的一个实现类

1.HashTable的方法是同步的,HashMap未经同步 

2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。 

3.HashTable有一个contains(Object value),功能和containsValue(Object value)功能一样。 

4.HashTable使用Enumeration,HashMap使用Iterator。 

 

问题2:如何HashMap同步?

法1、Collections.synchronizedMap(Map m)

法2、使用ConcurrentHashMap

 

详述:

LinkedList:

 

private transient Entry<E> header = new Entry<E>(null, null, null);  
	
public LinkedList() {  
        header.next = header.previous = header;  
}  

 

private static class Entry<E> {  
		E element;  
		Entry<E> next;  
		Entry<E> previous;  
	  
		Entry(E element, Entry<E> next, Entry<E> previous) {  
			this.element = element;  
			this.next = next;  
			this.previous = previous;  
		}  
    } 

 

//默认的添加动作,可以看到这个方法是把新元素添加 到表尾  
	 public boolean add(E e) {    
		addBefore(e, header); //加到头结点之前 ,即表尾    
		 return true;    
	 }    
		 

	 //默认的删除动作是删除链表的第一个元素,所以说在默认情况下,LinkedList其实扮*演的是一个队列的角色  
	 public E remove() {    
		 return removeFirst();    
	 } 	

	public E get(int index) {  
        return entry(index).element;  
    }  

 

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;    
    } 
	
 
	//	根据给定的索引值离表头近还是离表尾近决定从头还是从尾开始遍历  
    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;    
	} 


	//从表头开始遍历,返回此元素在表中的第一个位置  
    public int indexOf(Object o) {    
         int index = 0;    
         if (o==null) { //如果传入的元素是null,则不能调用 eqauls方法进行比较    
             for (Entry e = header.next; e != header; e = e.next) {    
                 if (e.element==null)    
                     return index;    
                 index++;    
             }    
         } else {    
             for (Entry e = header.next; e != header; e = e.next) {    
                 if (o.equals(e.element))    
                     return index;    
                 index++;    
             }    
         }    
         return -1;    
     }

 

注意entry的循环:

       for (Entry e = header.previous; e != header; e = e.previous) {}  

 

新节点的创建: 

Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  

 

此时新加节点已知道其前后节点,但其前节点并不知道后节点发生变化,后节点也不知道前节点发生变化,所以分别将新节点赋给他们。

 

 

HashMap:

        put -> addEntry(新建一个Entry)

        get

        getEntry

        //get与getEntry的区别在于一个返回的是Entry对象,一个返回的是Entry对象中的Value

 

LinkedHashMap:

       put -> addEntry(重写)

                新建一个Entry,然后将其加入header前

                e.addBefore(header)

 

       get -> 调用HashMap的getEntry - recordAccess(重写)

 

Hashtable:

      public class Hashtable<K,V>  extends Dictionary<K,V>  implements Map<K,V>, Cloneable, java.io.Serializable 

 

抽象类Dictionary 已过时,新的实现应该实现 Map 接口,而不是扩展此类。

 

 

 

HashMap:

//public class HashMap<K,V>  extends AbstractMap<K,V>  implements Map<K,V>, Cloneable, Serializable
 
transient Entry[] table;
 
 
static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        Entry<K,V> next;  
        final int hash;  
  
        Entry(int h, K k, V v, Entry<K,V> n) {  
            value = v;  
            next = n;  
            key = k;  
            hash = h;  
        }  
} 

 

final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

 

 

LinkedHashMap:

//其实LinkedHashMap几乎和HashMap一样,不同的是它定义了一个Entry<K,V> header,这个header不是放在Table里,它是额外独立出来的。LinkedHashMap通过继承hashMap中的Entry<K,V>,并添加两个属性Entry<K,V>  before,after,和header结合起来组成一个双向链表,来实现按插入顺序或访问顺序排序。

 

//public class LinkedHashMap<K,V>  extends HashMap<K,V>   implements Map<K,V>
 
private transient Entry<K,V> header;  
private final boolean accessOrder;
  
void init() {  
   header = new Entry<K,V>(-1, null, null, null);  
   header.before = header.after = header;  
} 
 
public LinkedHashMap(int initialCapacity, float loadFactor) {  
   super(initialCapacity, loadFactor);  
   accessOrder = false;  
} 

 

private static class Entry<K,V> extends HashMap.Entry<K,V> {
       
        Entry<K,V> before, after;
 
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
        
        private void remove() {
            before.after = after;
            after.before = before;
        }
      
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
        
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
    }

 

//遍历
//for (Entry e = header.after; e != header; e = e.after)  
public boolean containsValue(Object value) {         
        if (value==null) {  
            for (Entry e = header.after; e != header; e = e.after)  
                if (e.value==null)  
                    return true;  
        } else {  
            for (Entry e = header.after; e != header; e = e.after)  
                if (value.equals(e.value))  
                    return true;  
        }  
        return false;  
    }  

 

//LinkedHashMap的get()方法调用的是HashMap的getEntry - recordAccess(重写)

 

//get与getEntry的区别在于一个返回的是Entry对象,一个返回的是Entry对象中的Value

 

 

 

3、

分享到:
评论

相关推荐

    java常用集合类总结

    "Java集合类总结" Java集合类是Java语言中的一种重要数据结构,用于存储和管理数据。Java集合类可以分为两种:Collection接口和Map接口。Collection接口有两个子接口:List接口和Set接口。List接口是有序的,可以...

    java集合分类总结.doc

    Java集合分类总结 Java集合分类总结是Java语言中的一种容器,用于存储和管理多个对象。集合可以自动扩容,部分集合允许存放不同类型的元素。集合的主要分类有List、Set、Map等。 List集合是一种有序列表,允许存放...

    Java集合类总结

    ### Java集合类总结 #### 一、概述 Java集合类框架是Java标准库的一个重要组成部分,主要用于存储和处理数据集合。这些集合类被定义在`java.util`包中,为开发者提供了灵活的数据结构来实现各种应用程序的需求。...

    (zz)java集合类总结

    ### Java集合类总结 在Java开发中,集合类(Containers)是极其重要的组成部分,它们作为开发者日常编程不可或缺的工具,不仅让代码变得更加简洁、高效,还能显著提升程序的功能性和灵活性。本文将对Java标准类库中...

    JAVA集合类总结[整理].pdf

    JAVA集合类总结[整理].pdf

    java集合类总结

    在Java中,集合主要分为两大类:Collection和Map。本文将对Java集合框架中的Collection接口及其相关接口、类进行深入的探讨。 首先,Collection接口是所有单值容器的基础,它是Set、List和Queue接口的父接口。...

    java中的集合类总结

    以下是对标题和描述中提到的Java集合类的详细总结: 首先,所有Java集合类都继承自`java.util.Collection`接口。`Collection`接口是所有集合框架的基础,它定义了集合的基本操作,如添加、删除和遍历元素。`...

    Java集合类详解总结

    ### Java集合类详解总结 在Java编程中,集合框架(Collection Framework)是处理一组对象的强大工具,它提供了标准的数据结构来存储和操作这些对象。Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`...

    JAVA集合类用法总结

    Java集合类是Java编程语言中不可或缺的一部分,它们提供了一种高效、灵活的方式来存储和操作对象。集合类的主要接口包括Collection、List、Set和Map,这些接口定义了各种操作集合对象的方法,比如添加、删除、修改和...

    java集合类面试题总结

    Java 集合类面试题总结 Java 集合类是 Java 语言中的一种重要组件,用于存储和操作数据。下面总结了 Java 集合类的一些常见问题和答案。 HashMap 和 Hashtable 的区别 HashMap 和 Hashtable 都是 Java 中的散列表...

    集合类的总结

    本文将全面总结常用的集合类,并通过实际示例深入理解它们的使用。 首先,我们要了解集合框架的基础,它由`java.util`包中的接口和类构成。这些接口包括`Collection`、`List`、`Set`、`Queue`等,而类则如`...

    Java集合框架总结

    抽象类如`AbstractCollection`、`AbstractList`、`AbstractSet`和`AbstractMap`等为具体的集合类提供了一定程度的实现。这些抽象类可以减少重复编码的工作量,使开发者更容易创建自己的集合类。 #### 五、迭代器...

    java集合类知识总结--思维导图文件xmind

    java集合类知识总结--思维导图文件xmind xmind文件类型 总结了java常用集合相关问题 包括map、set、list、数组等

    泛型集合类的大概应用

    根据给定的信息,本文将详细解释“泛型集合类的大致应用”,重点在于Java中的泛型集合类,如`ArrayList`、`HashMap`等,并结合实际代码示例进行讲解。 ### 泛型集合类概述 在Java编程语言中,集合框架提供了一组...

    第13讲 JAVA集合类.ppt

    总结来说,Java集合类通过提供丰富的接口和实现,使得Java开发者可以灵活选择适合特定需求的数据结构,提高代码的可读性和性能。理解并熟练掌握这些集合类和接口,对于编写高质量的Java程序至关重要。

    【Java面试+Java学习指南】 一份涵盖大部分Java程序员所需要掌握的核心知识

    Java集合类总结 Java集合详解1:一文读懂ArrayList,Vector与Stack使用方法和实现原理 Java集合详解2:Queue和LinkedList Java集合详解3:Iterator,fail-fast机制与比较器 Java集合详解4:HashMap和HashTable Java...

    集合类框架

    集合类框架总结 其中介绍了Collection Arraylist List Map

Global site tag (gtag.js) - Google Analytics