`
greemranqq
  • 浏览: 975407 次
  • 性别: Icon_minigender_1
  • 来自: 重庆
社区版块
存档分类
最新评论

JAVA深入集合--HashTable

阅读更多

一、介绍

       Hashtable 是早期实现的一个哈希存储方式的类,也就是键值对(key-value)的存放方式。实际上市键值对 和 链表的组合,相对同步安全的。

     特点:

            1.是key-value 方式存放的,并且是无序存放的

            2.线程安全的,性能较低

            3.key 不允许重复,否者会覆盖数据

            4.key 不能为null,否者会空指针异常,

 

二、源码解析

      

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable 

   

 

    1.继承了Dictionary,实现 Map接口,和 Cloneable,这里简单说一下。

    Dictionary:JDK 1.6阐明是一个过时的,用于存键值对的抽象父类,定义了一些基本属性,有兴趣自己看API。后来建议去实现Map 接口,而不是扩展此类,估计是面向接口编程,怕太臃肿了。只有hashtable继承,不是到有啥用,早就该去掉了。

 

    Map :作为代替Dictionary 的出现,也是定义了键值对的一些方法,好处是便于各种键值对的类自己去实现,让代码更轻了。

   Cloneable: 是克隆需要,Vactor 已经说了,就不多讲了。

 

   2.主要构造方法:

     

// 我们获得的hashtable对象,无论有参数,无参数的 最终都调用的这个构造。
// 参数说明:
// initialCapacity : 初始容量,好比新建数组,最开始的长度多少,默认11
// loadFactor:增长因子,默认是0.75f,好比是 你的内容超过了 总长度了75%,就会自动扩容
public Hashtable(int initialCapacity, float loadFactor) {
        // 初始长度小于0 必然异常
	if (initialCapacity < 0)
	    throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        // 同上
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
        
        if (initialCapacity==0)
            initialCapacity = 1;
        
	this.loadFactor = loadFactor;

        // table  实际上是  private transient Entry[] table;
        // Entry 是一个内部键值对的内部类,下面说
        // 可以看到,hashTabale 实际上就是一个  Entry[]的数组
	table = new Entry[initialCapacity];
        // 这里就是扩容的位置了,也就是会说你的数组容量超过了 下面这个数,默认就会扩容了
	threshold = (int)(initialCapacity * loadFactor);
    }

  

    3.内部类Entry 解析:

    

 private static class Entry<K,V> implements Map.Entry<K,V> {
	int hash;
	K key;
	V value;
        // 链表的动作,Map 实际有键值对和链表组成,具体的将hash算法再讨论
	Entry<K,V> next;

 

 

  这里可以看到,这里是实现了Map.Entry 接口,定义了一些泛型属性,我们先看这个接口:

// Map 里面的内部接口
interface Entry<K,V> {
	K getKey();
	V getValue();
	V setValue(V value);
	boolean equals(Object o);
	int hashCode();
    }
}

 

  

// HashTable 内部类的主要方法。
	public K getKey() {
	    return key;
	}

	public V getValue() {
	    return value;
	}

	public V setValue(V value) {
	    if (value == null)
		throw new NullPointerException();

	    V oldValue = this.value;
	    this.value = value;
	    return oldValue;
	}

	public boolean equals(Object o) {
	    if (!(o instanceof Map.Entry))
		return false;
	    Map.Entry e = (Map.Entry)o;

	    return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
	       (value==null ? e.getValue()==null : value.equals(e.getValue()));
	}

	public int hashCode() {
	    return hash ^ (value==null ? 0 : value.hashCode());
	}

    }

 

     这里可能有些疑惑,既然实现了Map 接口,里面的getKey,getValue 等方法,为什么要用内部类去实现Map 的Entry接口,从而进行实现呢?不是很麻烦吗?

     这里我的理解是:提供了一个包含键值对的映射集,这东西更加方便我们进行迭代(遍历),提供一种统一的迭代方式(Iterator),我们获得这个映射之后,可以同时获得 单个的键和值,并且迭代期间任何非自身的操作,都会报错,保证这个映射的唯一性,当然只能通过内部setValue(),进行设置值。

      同时这个键值对在其他地方 有很灵活的使用,让你获得键 值 等个各种方式,更加灵活,后面会有

      

      其实HashTbale 自身提供了 获得key 和value 的方式,请看源码:

      

// 获得values
private transient volatile Collection<V> values = null;
 

 

   

// 这是获得所有值的方式
public Collection<V> values() {
	if (values==null)
        // 这里是通过一个内部,和 当前hashMap 对象,通过collection 方法获得值的集合
        // 这里使用的是线程安全的方法
	    values = Collections.synchronizedCollection(new ValueCollection(),
                                                        this);
        return values;
    }

    private class ValueCollection extends AbstractCollection<V> {
        public Iterator<V> iterator() {
	    return getIterator(VALUES);
        }
        public int size() {
            return count;
        }
        public boolean contains(Object o) {
            return containsValue(o);
        }
        public void clear() {
            Hashtable.this.clear();
        }
    }
 

 

    顺便看看Collections.synchronizedCollection 源码:

  

static <T> Collection<T> synchronizedCollection(Collection<T> c, Object mutex) {
	return new SynchronizedCollection<T>(c, mutex);
    }

final Collection<E> c;  // Backing Collection
	final Object mutex;     // Object on which to synchronize

// 这里就只有一个赋值操作
SynchronizedCollection(Collection<E> c, Object mutex) {
	    this.c = c;
            this.mutex = mutex;
        }
 

 

   从代码上看,相当于是把 ValueCollection 这个内部类 和hashtable 传入进去赋值给对象了。

   1.ValueCollection 里面有iterator(),size() 等方法。这里相当于colleaction 方法里面有几乎所有

     集合的基本方法接口,然后实现在各个集合里面。但是集合里面定义内部类 同样调用实现那些实现方      法的作用是为了将内部类 传回给colleaction ,让集合具有一种通用的访问这些元素的方法。

   比如:Collection 定义集合可以看电影。hashtable 实现 用电脑看电影。 然后定义内部类,里面把用电脑看电影这种方式也放进去,然后可以送给Collection 集合,那么它就可以知道是用电脑看电影了。 也就是说,看电影这种举动很多集合都有,Collection 作为一种工具,只要任何其他集合传入一个方式过来,就可以调用各自的看电影的方式了。

    2.参数this,实际上是一把对锁,实现线程安全的。这里看Collection 里面对这个内部类的操作就知道

 

    

// 这是获得,key 的集合
private transient volatile Set<K> keySet = null;
// 上面的key,values
private transient volatile Set<Map.Entry<K,V>> entrySet = null;
  
 public Set<K> keySet() {
	if (keySet == null)
	    keySet = Collections.synchronizedSet(new KeySet(), this);
	return keySet;
    }

    private class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
	    return getIterator(KEYS);
        }
        public int size() {
            return count;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        // 多一个方法
        public boolean remove(Object o) {
            return Hashtable.this.remove(o) != null;
        }
        public void clear() {
            Hashtable.this.clear();
        }
    }
 

 

  这里你会发现,获得keys 和values方法几乎一样,只是这里多提供了一个remove 方法,

  那么这两个相同的方法  是如何 分别获得key 和value 的呢?请看:

  

// 这是主要不同点:
public Iterator<K> iterator() {
	    return getIterator(KEYS);
        }

public Iterator<K> iterator() {
	    return getIterator(VALUES);
        }
 // 这几个参数 对应了 ,返回的类型,表示 枚举
 private static final int KEYS = 0;
 private static final int VALUES = 1;
 private static final int ENTRIES = 2;

 

   

// 方法,发现这里其实是返回的是一个内部类, count = 0 的也是内部类,这里不介绍了 ,里面就判// 定空值的,主要看Enumerator
 private <T> Iterator<T> getIterator(int type) {
	if (count == 0) {
	    return (Iterator<T>) emptyIterator;
	} else {
	    return new Enumerator<T>(type, true);
	}
  

 

   

private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
        // 里面的数组
	Entry[] table = Hashtable.this.table;
	int index = table.length;
        // 键值对方式,内部类
	Entry<K,V> entry = null;
	Entry<K,V> lastReturned = null;
        // 类型
	int type;
....
....
// 构造
Enumerator(int type, boolean iterator) {
	    this.type = type;
	    this.iterator = iterator;
	}
   
   下面继续看看 type 这里在哪使用的:
// 在 获得下一个元素的时候 就能使用了	
public T nextElement() {
	    Entry<K,V> et = entry;
	    int i = index;
            // 将当前数组 给这个变量
	    Entry[] t = table;
	    /* Use locals for faster loop iteration */
            // 循环遍历 数组,并将数组里面的Entry<K,V> 类型的元素赋值
	    while (et == null && i > 0) {
		et = t[--i];
	    }
	    entry = et;
	    index = i;
	    if (et != null) {
		Entry<K,V> e = lastReturned = entry;
                // 获得为Entry<K,V> 类型的键值对
		entry = e.next;
                // 这里就可以返回 键  值  还是键值对了。这就明白当初定义内部类 Entry好处
		return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
	    }
	    throw new NoSuchElementException("Hashtable Enumerator");
	}
  
   当然还有我们常用的键值对 遍历方式:
public Set<K> keySet() {
	if (keySet == null)
	    keySet = Collections.synchronizedSet(new KeySet(), this);
	return keySet;
    }
  包括获得枚举类型key 的方式:
 public synchronized Enumeration<K> keys() {
	return this.<K>getEnumeration(KEYS);
    }
  看到这里相信你会发现,所有的都是通过 内部类Enumerator<T> 操作内部类 Entry 完成的。而提供的各种实现方式,也是通过内部类送到各种集合里面,统一的接口方法(size() 等等),这就完成了各种类型的集合,可以通过迭代器统一遍历。
   下面介绍一下hashtable 其他的常用方法源码: 
   1.put(K key,V value):存放的方法
     
 public synchronized V put(K key, V value) {
	// Make sure the value is not null
        // 这里说明了值不能为空的
	if (value == null) {
	    throw new NullPointerException();
	}

	// Makes sure the key is not already in the hashtable.
	Entry tab[] = table;
        // 下面实际上通过 一些算法计算存放位置,具体hash 等算法的研究,以后专门讲解
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            //  这里通过hash 和 值的比较,如果重复就覆盖
	    if ((e.hash == hash) && e.key.equals(key)) {
		V old = e.value;
		e.value = value;
		return old;
	    }
	}
        
	modCount++;
        // 超过临界值,从新 计算
	if (count >= threshold) {
	    // Rehash the table if the threshold is exceeded
	    rehash();

            tab = table;
            index = (hash & 0x7FFFFFFF) % tab.length;
	}
        // 存放值
	// Creates the new entry.
	Entry<K,V> e = tab[index];
	tab[index] = new Entry<K,V>(hash, key, value, e);
	count++;
	return null;
    }
 
   2. get(Object key):通过键 获得值的方法:
  public synchronized V get(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
        // 和上面差不多,计算位置的
        // PS:JDK 这里写得重复了, 代码还是可以提炼的嘛  呵呵
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		return e.value;
	    }
	}
	return null;
    }
 
   3.containsValue(Object value),实际就是contains(Object value)
    
public synchronized boolean contains(Object value) {
	if (value == null) {
	    throw new NullPointerException();
	}

	Entry tab[] = table;
        // 说白了就是一个Entry 内部元素遍历。简单的说 就是数组遍历啦
	for (int i = tab.length ; i-- > 0 ;) {
	    for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
		if (e.value.equals(value)) {
		    return true;
		}
	    }
	}
	return false;
    }
 
   4. containsKey(Object key)
public synchronized boolean containsKey(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
        // 其实还是Entry 元素访问,数组遍历,当然这里 对key 进行了hash 比较,有些位置重复嘛
        // PS:看来重复代码比较多,hashmap 估计会好很多
	for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		return true;
	    }
	}
	return false;
    }
 
  差不多 就介绍完了,其他方法,都类似的。
  总结:
  1.hashtable 是一种键值对存放的数据结构
  2.它是有一个内部类 Entry 的的形式存放,将所有元素以Entry<K,V> 方式存放在数组table里面。
  3.对集合的遍历都是通过内部类Enumerator 进行,并且Enumerator 其实操作的也是table数组,操作的也是Entry 。
  4.这里面类的设计方法 还是比较灵活,值得学习和借鉴,内部类的使用,以及接口的各种实现。
  5.PS:index 计算代码重复,而且计算方式过于简单,我们平时设计 应该设计成尽量不重复的hashcode.
至于hash 算法的研究,以后专门讲解。写得不好的地方希望,大家批评指正!小弟一定虚心修改!

      

分享到:
评论

相关推荐

    精通java集合框架--List,Set..

    本文将深入探讨Java集合框架的核心概念,包括`List`、`Set`、`Map`以及它们之间的区别和联系。 #### Java集合框架简介 Java集合框架是Java平台的一部分,它由一系列接口组成,这些接口描述了不同类型的容器,比如...

    (超赞)JAVA精华之--深入JAVA API

    ### 深入Java API #### 一、Java SE **1.1 深入 Java API** **1.1.1 Lang包** - **String类与 StringBuffer类** - `String` 类不可变,一旦创建后其内容无法更改;而 `StringBuffer` 类则允许在原有基础上修改...

    java软件技术文档-深入java8的集合5:Hashtable的实现原理.pdf

    【Java软件技术文档-深入Java8的集合5:Hashtable的实现原理】 在Java编程语言中,集合框架是不可或缺的一部分,而Hashtable是其中一种古老的、线程安全的哈希表实现。尽管现在更多地使用HashMap或...

    java Hashtable的泛型化

    让我们深入了解一下`Hashtable`的泛型使用: 1. **类型安全**:使用泛型`Hashtable`可以防止不兼容类型的对象被放入容器,从而消除运行时的类型检查和转换,提高了代码的可读性和安全性。 2. **编译时错误检测**:...

    哈希表-使用Java开发的哈希表-HashTable.zip

    尽管现在已经被`HashMap`所替代,但理解`HashTable`的工作原理和特性仍然对深入理解Java集合框架以及数据结构有重要意义。 哈希表的核心在于哈希函数,它将键(Key)转化为数组的索引位置。理想情况下,哈希函数应...

    【IT十八掌徐培成】Java基础第11天-04.Map集合-集合整理.zip

    本教程“Java基础第11天-04.Map集合-集合整理”由IT十八掌徐培成讲解,旨在深入解析Map集合的使用和特性。 首先,Map接口中的核心方法包括: 1. `put(key, value)`: 向Map中添加一个键值对。如果键已存在,则会...

    java面试汇总--提高成功率的宝典

    Java面试汇总——提升面试成功率的关键知识点 在Java面试中,掌握关键知识点是成功的关键。以下是一些常见的面试问题和解答,这些内容可以帮助你更...同时,不断实践和深入理解这些知识点,才能在实际开发中游刃有余。

    Java 实例 - 遍历 HashTable 的键值源代码+详细教程.zip

    这个压缩包“Java 实例 - 遍历 HashTable 的键值源代码+详细教程.zip”包含了关于如何遍历`HashTable`的详细教程和源代码,对于学习Java的初学者或者需要深入了解`HashTable`操作的开发者来说,这是一个非常宝贵的...

    java 集合----Map、Collection

    Java集合框架是编程中不可或缺的一部分,它提供了多种数据结构,如列表(List)、集(Set)以及映射(Map),便于我们高效地存储、管理和操作数据。本文将深入探讨Map和Collection接口,以及它们的实现类,特别是HashSet和...

    java-se-summary-JavaSE相关的总结文章

    4. **集合框架**:Java集合框架是存储和管理对象的工具,包括List(ArrayList、LinkedList)、Set(HashSet、LinkedHashSet、TreeSet)和Map(HashMap、TreeMap、Hashtable)。泛型的引入增强了类型安全,避免了强制...

    Java程序员集合框架面试题-java集合框架面试题.docx

    Java集合框架是Java编程语言中的核心部分,它提供...面试中,深入理解这些概念,以及如何在实际应用中选择合适的集合类型,是评估Java程序员技能的关键。了解并熟练运用Java集合框架,可以编写出更高效、可维护的代码。

    Java学习资料-核心知识

    Java的核心知识是每个开发者必须掌握的基础,这包括了对Java集合框架的深入理解。Java集合框架是Java库中的一组接口和类,提供了存储和操作对象的统一方式。 首先,Java集合框架的两个主要接口是`Collection`和`Map...

    Java知识总结--CoreJava.doc

    本文将深入探讨Java的核心特性,包括基本数据类型、异常处理、集合框架、多线程以及一些常见的编程概念。 1. **Java基本数据类型及所占位数** Java提供了八种基本数据类型,分为四类: - 整数类型:byte(1字节)...

    JAVA DEVELOPMENT KIT-118-doc

    Java Development Kit(JDK)是Java...通过阅读"jdk118-doc"中的文档,开发者可以深入了解这个版本的特性和使用方式,尽管现代开发通常使用更新的Java版本,但了解历史版本有助于理解Java语言的发展历程和设计理念。

    Java集合框架总结

    本文档将深入探讨Java集合框架的关键组成部分、它们之间的关系以及如何有效地使用它们。 #### 二、Java集合框架结构 Java集合框架的核心部分包括以下几类: - **集合接口**:主要包括`Collection`、`Set`、`List`...

    java练习题--容器使用练习

    本练习题旨在帮助你深入理解和熟练掌握Java中的容器使用,特别是其核心类库`java.util`中的ArrayList、LinkedList、HashSet、HashMap等。通过解决这些练习题,你将能够更好地了解容器的基本操作,如添加、删除、查找...

    Java集合详解,详细讲解java的集合类

    本文将深入讲解Java集合类,特别是Collection接口和其下的List、Set,以及Map接口中的几个重要实现类。 首先,我们来看Collection接口。Collection是最基本的集合接口,它代表一组Object,即它的元素。Collection...

    java程序设计--实验报告(5)

    1. **列表对象**:在Java中,列表是一种有序的数据集合,可以存储重复元素。Java提供了一些接口和类来实现列表,如List接口和ArrayList、LinkedList等实现类。`ArrayList`是基于数组实现的,提供快速的随机访问,而`...

Global site tag (gtag.js) - Google Analytics