Java Se ：Map 系列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

之前对Java Se中的线性表作了简单的说明。这一篇就来看看Map。

Map系列的类，并不是说所有的类都继承了Map接口，而是说他们的元素都是以<Key, Value>形式设计的。

Dictionary

这个类现在不推荐使用了，但也有必要说一下，在它的描述中，有这么一句：Any non-null object can be used as a key and as a value。

现在都改用Map接口了。

Map

这个接口用于替换Dictionary的。这种集合提供了三种视图方式：

1）a set of keys

2）collection of Values

3）set of Entry<key, value>

Hashtable

这个类继承了Dictionary实现了Map。下面就重点看看这个类如何实现。

从这里看Hashtable是一个数组，数组的元素是Entry。

在看看Entry的设计：

这个Entry是一个单链表。

所以Hashtable的数据结构就可以认为是这样的：

为什么会这样设计？

以为硬件的原因，支持数组和链表两种形式，所以其他的数据结构（集合）都是基于这两类基础结构实现的。

Hashtable的设计，关键一点是hash,它计算的是key的hash，通过key的hashcode来计算这个元素所在的单链表在数组中的索引，然后根据索引取到单链表，然后进行其他的操作。

接下来看看它的几个重要方法如何实现：

put

public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // 如果key已经在这个hashtable中存在，就覆盖原有的value，并返回原有的value。 // 从这一小段代码中，我们就可以看出hashtable的结构确实如上面所想的那样。Entry tab[] = table; int hash = key.hashCode(); 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)) { 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; } // 如果不存在，就把key value 封装成一个Entry，然后插入到相应位置// 在之前的代码中已经计算出它的索引了，接下来的任务就是把entry插入到数组索引位置处的单链表里。插入的时候是从头部插入的。 Entry<K,V> e = tab[index]; tab[index] = new Entry<K,V>(hash, key, value, e); count++; return null; }

Hashtable#put(key, value)

常用的方法get(key),remove(key)的方法就不分析了，因为没有必要，只要你了解了这个数据结构，自己就可以实现它的几个常用的方法。