本文分享给大家的是：

Source from Data Structures and Algorithms in Java, 6th Edition​learning.oreilly.com/library/view/data-structures-and/9781118771334/14_chap10.html#chap10

写过代码的应该都知道Map代表的就是键值对，那么在JAVA中，map的ADT应该可以实现一下方法：

书里接下来实现的是一个简化版的java.util.Map接口对于返回可迭代对象的entrySet，我们使用Entry接口来实现（java.util.Map则依赖于java.ut推广计划和推广单元il.Map.Entry对象。

注意get,put,remove方法会返回与当前k绑定的v，如果没有的话则返回null，这其实会有种k默认与null绑定的概念（因为如果你真的给k绑定了v为null的值，key还是会返回null所以java.util.Map

还是先了一个containsKey方法来专门判断k是否在map中。一个典型的map使用样例如下：

根据以上，我们可以设计出一个map的ADT接口：publicinterfaceMap{intsize();booleanisEmpty();Vget(Kkey);Vput(Kkey,Vvalue

);Vremove(Kk);IterablekeySet推广计划和推广单元();Iterablevalues();IterableentrySet();}Map的抽象基类后文将接着用其他数据结构来实现MAP的adt, 每种实现都有相应的优劣势。

我们首先设计一个AbstractMap的积累类提供map实现的通用方法，一个Map的基类应该支持如下操作：基于size来判断当前map是否为空的isEmpty一个内部类MapEntry来实现Entry接口。

基于entrySet方法的改进实现keySet以及values方法这样我们只需要实现entrySet就可以实现三种迭代方式了下面是具体的实现代码 publicabstractclassAbstractMap。

implemen推广计划和推广单元tsMap{publicbooleanisEmpty(){returnsize()==0;}protectedstaticclassMapEntryimplements

Entry{privateKk;privateVv;publicMapEntry(Kkey,Vvalue){k=key;v=value;}publicKgetKey(){returnk;}public

VgetValue(){returnv;}protectedvoidsetKey(Kkey){k=key;}protectedVsetValue(Vvalue){Vold=v;v=value;return

old;}}privatec推广计划和推广单元lassKeyIteratorimplementsIterator{privateIteratorentries=entrySet().iterator

();//reuse entrySet publicbooleanhasNext(){returnentries.hasNext();}publicKnext(){returnentries.next().

getKey();}//return key! publicvoidremove(){thrownewUnsupportedOperationException();}}privateclassKeyItera推广计划和推广单元ble

implementsIterable{publicIteratoriterator(){returnnewKeyIterator();}}publicIterablekeySet(){

returnnewKeyIterable();}privateclassValueIteratorimplementsIterator{privateIteratorentries

=entrySet().iterator();publicbooleanhasNext(){returnentries.hasNext();}publicVnext(){returnentries.next

().getValue(推广计划和推广单元);}publicvoidremove(){thrownewUnsupportedOperationException();}}privateclassValueIterable

implementsIterable{publicIteratoriterator(){returnnewValueIterator();}}publicIterablevalues()

{returnnewValueIterable();}}一个简单的Unsorted Map实现的我们接下来通过ArrayList类来对刚刚的抽象基类进行实现通过数组的实现，每次我们执行get,put,remove

方法的时候我们都需要对全推广计划和推广单元局扫描来确定某个k是否存在所以我们需要提供一个findIndex方法，来返回需要查询的k的位置其他方法的实现则较为简单有一个值的提一下的方法就是如何从map中移除一个值，虽然我们可以使用。

ArrayList的remvoe方法 ，但那样会导致所有的后续元素向前移动一位所以我们可以利用数组是无序的特点，当需要删除一个元素时候，直接当前列表中的最后一个元素移动到移除的这个元素的位置上即可这种实现其实很低效，基本所有的操作都需要O(N)的时间才能完成

，就当学习一下简单实现把：importjava.util.ArrayList;importjava.util.Iterator;importjava.ut推广计划和推广单元il.NoSuchElementException

;/** * An implementation of a map using an unsorted table. * * @author Michael T. Goodrich * @author Roberto Tamassia

* @author Michael H. Goldwasser */publicclassUnsortedTableMapextendsAbstractMap{/** Underlying storage for the map of 推广计划和推广单元entries. */

privateArrayListtable=newArrayList<>();/** Constructs an initially empty map. */public

UnsortedTableMap(){}// private utility /** Returns the index of an entry with equal key, or -1 if none found. */

privateintfindIndex(Kkey){intn=table.size();for(intj=0;j

j;return-1;// special value推广计划和推广单元 denotes that key was not found }// public methods /** * Returns the number of entries in the map.

* @return number of entries in the map */@Overridepublicintsize(){returntable.size();}/** * Returns the value associated with the specified key, or null if no suc推广计划和推广单元h entry exists.

* @param key the key whose associated value is to be returned * @return the associated value, or null if no such entry exists

*/@OverridepublicVget(Kkey){intj=findIndex(key);if(j==-1)returnnull;// not found returntable.get(j

).getValue();}/** * Associates the giv推广计划和推广单元en value with the given key. If an entry with * the key was already in the map, this replaced the previous value

* with the new one and returns the old value. Otherwise, a new * entry is added and null is returned.

* @param key key with which the specified value is to be associated 推广计划和推广单元 * @param value value to be associated with the specified key

* @return the previous value associated with the key (or null, if no such entry) */@Overridepublic

Vput(Kkey,Vvalue){intj=findIndex(key);if(j==-1){table.add(newMapEntry<>(key,value));// add new entry

returnnull;}else// key alread推广计划和推广单元y exists returntable.get(j).setValue(value);// replaced value is returned

}/** * Removes the entry with the specified key, if present, and returns its value. * Otherwise does nothing and returns null.

* @param key the key whose entry is to be removed from the map * @ret推广计划和推广单元urn the previous value associated with the removed key, or null if no such entry exists

*/@OverridepublicVremove(Kkey){intj=findIndex(key);intn=size();if(j==-1)returnnull;// not found Vanswer

=table.get(j).getValue();if(j!=n-1)table.set(j,table.get(n-1));// relocate last entry to hole created 推广计划和推广单元by removal

table.remove(n-1);// remove last entry of table returnanswer;}//---------------- nested EntryIterator class ----------------

privateclassEntryIteratorimplementsIterator{privateintj=0;publicbooleanhasNext(){returnj<

table.size();}publicEntrynext(){if(j==table.size())thrownewNoSuchElem推广计划和推广单元entException("No further entries"

);returntable.get(j++);}publicvoidremove(){thrownewUnsupportedOperationException("remove not supported"

);}}//----------- end of nested EntryIterator class ----------- //---------------- nested EntryIterable class ----------------

privateclassEntryIterableimple推广计划和推广单元mentsIterable{publicIteratoriterator(){returnnew

EntryIterator();}}//----------- end of nested EntryIterable class ----------- /** * Returns an iterable collection of all key-value entries of the map.

* * @return iterable collection of the maps entries */@Overridepublic推广计划和推广单元IterableentrySet

(){returnnewEntryIterable();}}哈希表Hash Tables刚刚的实现很低效，我们接下来看看实现map最搞笑的一种数据结构：哈希表（Hash Table）直观上看，一个map数据结构支持将我们的key抽象成。

地址的概念。举个例子，我们有一个元素数量为n的table,那么序列就是0到N-1，我们就可以使用一个长度为N的look up table来进行元素位置的查询：

通过这种表达，我们将index与key同化成了一个概念，所以通过这种方式我们的get,put,remove都可以达到O(1)的效率但这样子会有两种限制：当N >= n时候，如推广计划和推广单元何灵活的拓展存储边界K不一定总是整数。

所以我们引入hashtable中最强大的概念：HASH FUNCTION它的作用就在于将其他类型的key通过一个hash function变成一个整数，然后通过数组索引去直接搜寻元素理想情况下，keys会被这个hash function均匀的分散到N个index中。

但实际上很有可能出现2个元素的K被hashed成了同一个value出现碰撞这种情况下我们可以再次提供一个bucket array的概念，每个bucket都能针对同一个key维护一个索引列表（看下图应该就能理解了）。

哈希函数（hash function） 哈希函数的目的在于将每个key能投射成为一推广计划和推广单元个在[0,N-1]范围内的整数N代表目前这个hash table的整体容量所以我们的k,v存储结构就变为了一个通过哈希变换的索引h = f(k)在数组上的定位，即将entry(k,v)存储在A[h(k)]中。

如果有多个Key共享一个hash value，两个值就会被投射到同一个桶A内（哈希函数应该尽量避免这种冲撞的情况出现）一般我们会将哈希函数分成两部分来进行解读：第一部分是通过hash function将输入k映射成一个hash code。

以及一个压缩函数（compression function）将hash code映射成为一个0-N的整数（通过下图理解

这样子分阶段进行区分的好处在于将计算推广计划和推广单元hash code的部分与实际映射到数组大小的部分进行拆分这样子我们就可以设计一个更general的hash code；只有压缩函数的部分会受到实际存储大小的制约Hash Code

我们从次一步开始讲起，hash code并不要求一定要将k映射到目前table的存储限制内（甚至可能是负数），我们希望hash code能做到的就是尽可能的避免不同k之间的hash 冲撞因为如果在这一步就重装了，那么在后续压缩这一步就更没办法做处理了。

接下来先从原理的角度来理解hash code在java中的hash code是通过32-bit hash code实现的，所以对于基础类型byte short int等推广计划和推广单元我们都可以通过将其转型为int来得到衣蛾不错的hash code。

对于任何基类为float的数据类型，我们可以通过Float.floatToIntBits(x)来得到其证书的bit表达对于bit长度比整数长的数据类型（long, double)，就不能通过上面的方法付了。

我们可以使用high-oder 32bits来对原来的信息进行切割后再转型（会有不可避免的重装）下面的暂时看不懂，先放过来把

多项式hash code Polynomial Hash Codes 上面的方法对于字符或者其他变量的数据类型不太友好如果我们仅仅讲数组的hash code相加来hash的话，像是temp01和temp1推广计划和推广单元0将共享同一个hash code,所以我们还需要将多字符的顺序考虑进去。

所以书中提出了另一种hash code：选取一个非0常量 a!=1，使用以下项作为hash code：

数学上来说这就是个a的多项式，所以这种哈希函数就叫做polynomial hash code。我们可以通过如下方法计算hash code:

可以发现这种方法是通过相乘来协调每个字符串在不同位置的影响当然在一般的电脑上，过长的字符串会造成hash code的over flow（所以选对a很重要）书中接下来说试验表明 33,37,39,41 对于英语语言一般来说是比较好的a值。

Java中的hash codejava中哈希表的作用推广计划和推广单元非常关键，Object作为所有类的祖先，有一个默认的hashCode方法（返回一个32-bit integer 作为hash code）. 默认的哈希方法一般返回的就是从对象的内存地址的整数表达。

但是我们对于hashCode()的使用也需要小心，因为hash code一定需要满足相同的key的hash code能够相同，不同的key返回的hash code需要不同（肯定不想索引k1得到k2).所以我们得到如下hash code需要满足的定义：

ifx.equals(y)thenx.hashCode()==y.hashCode() 举个例子，java的String类定义了equals方法来匹配2个推广计划和推广单元字符串对象包含的字符是否相同对应的hash code也一定需要保持一致。

压缩函数 Compression function的一般的哈希函数没办法直接满足映射需求，因为返回的整数可能会超过对应的数组限制，所以一旦我们确定了需要的hash 函数，如何将hash code映射成数组的索引也是很有讲究的。

好的压缩函数能够最大限度的减少冲撞取余法 the division method一个简单的压缩函数就是取余法，我们把整数i映射为 i mod N , N代表数组大小如果我们选择N是一个素数的话，它能够更好的帮助我们减少冲撞。

The MAD Method还有一个更高级的Multiply-Add-and-推广计划和推广单元Divide，它会将证书映射为：

where N is the size of the bucket array, p is a prime number larger than N, and a and b are integers chosen at random from the interval [0,

p − 1], with a > 0. This compression function is chosen in order to eliminate repeated patterns in the set of hash codes and get us closer to hav推广计划和推广单元ing a “good” hash function, that is, one such that the probability any two different keys collide is 1/

N. This good behavior would be the same as we would have if these keys were “thrown” into A uniformly at random.(懒得翻了)

书中接下来介绍了如何handle Key的冲撞，但内容已经够长了就先不先写在这里了（我估计以后自己也不会再看了hhh)最后来看下目前写到这儿的哈希表的运算效率推广计划和推广单元和我们一开始以列表为基础的方式对比：

实现一个hash map （终于啊）对比上面的map，我们如果实现一个hashmap还需要额外支持一下方法：

What the AbstractHashMap class does provide is mathematical support in the form of a hash compression function using a randomized Multiply-Add-and-Divide (MAD) formula, and support for automatically resizing the underlying hash 推广计划和推广单元table when the load factor reaches a certain threshold.

The hashValue method relies on an original keys hash code, as returned by its hashCode() method, followed by MAD compression based on a prime number and the scale and shift parameters that are randomly chosen in the constructor.

importjava.util.A推广计划和推广单元rrayList;importjava.util.Random;/** * An abstract base class supporting Map implementations that use hash

* tables with MAD compression. * * The base class provides the following means of support: * 1) Support for calculating hash values with MAD compression

* 2) Suppor推广计划和推广单元t for resizing table when load factor reaches 1/2 * * Subclass is responsible for providing abstract methods:

* createTable(), bucketGet(h,k), bucketPut(h,k,v), * bucketRemove(h,k), and entrySet() * and for accurately maintaining the protected member, n,

* to reflect ch推广计划和推广单元anges within bucketPut and bucketRemove. * * @author Michael T. Goodrich * @author Roberto Tamassia

* @author Michael H. Goldwasser */publicabstractclassAbstractHashMapextendsAbstractMap{protected

intn=0;// number of entries in the dictionary protectedintcapacit推广计划和推广单元y;// length of the table privateintprime

;// prime factor privatelongscale,shift;// the shift and scaling factors /** Creates a hash table with the given capacity and prime factor. */

publicAbstractHashMap(intcap,intp){prime=p;capacity=cap;Randomrand=newRandom();scale=rand.next推广计划和推广单元Int(prime

-1)+1;shift=rand.nextInt(prime);createTable();}/** Creates a hash table with given capacity and prime factor 109345121. */

publicAbstractHashMap(intcap){this(cap,109345121);}// default prime /** Creates a hash table with capacity 17 and prime factor 109345121. */

publicAbstractHashMap推广计划和推广单元(){this(17);}// default capacity // public methods /** * Tests whether the map is empty.

* @return true if the map is empty, false otherwise */@Overridepublicintsize(){returnn;}/** * Returns the value associated with the specified key, or null if no such entry 推广计划和推广单元exists.

* @param key the key whose associated value is to be returned * @return the associated value, or null if no such entry exists

*/@OverridepublicVget(Kkey){returnbucketGet(hashValue(key),key);}/** * Removes the entry with the specified key, if present, and returns

* its associated推广计划和推广单元 value. Otherwise does nothing and returns null. * @param key the key whose entry is to be removed from the map

* @return the previous value associated with the removed key, or null if no such entry exists */

@OverridepublicVremove(Kkey){returnbucketRemove(hashValue(key),key);}/** 推广计划和推广单元 * Associates the given value with the given key. If an entry with

* the key was already in the map, this replaced the previous value * with the new one and returns the old value. Otherwise, a new

* entry is added and null is returned. * @param key key with which the specified value推广计划和推广单元 is to be associated

* @param value value to be associated with the specified key * @return the previous value associated with the key (or null, if no such entry)

*/@OverridepublicVput(Kkey,Vvalue){Vanswer=bucketPut(hashValue(key),key,value);if(n>capacity/2)// keep load factor <= 0.5

resize(2*c推广计划和推广单元apacity-1);// (or find a nearby prime) returnanswer;}// private utilities /** Hash function applying MAD method to default hash code. */

privateinthashValue(Kkey){return(int)((Math.abs(key.hashCode()*scale+shift)%prime)%capacity);}/** Updates the size of the hash table and rehashes al推广计划和推广单元l entries. */

privatevoidresize(intnewCap){ArrayListbuffer=newArrayList<>(n);for(Entrye:entrySet())

buffer.add(e);capacity=newCap;createTable();// based on updated capacity n=0;// will be recomputed while reinserting entries

for(Entrye:buffer)put(e.getKey(),e.getValue());}// protected abstract 推广计划和推广单元methods to be implemented by subclasses

/** Creates an empty table having length equal to current capacity. */protectedabstractvoidcreateTable

();/** * Returns value associated with key k in bucket with hash value h. * If no such entry exists, returns null.

* @param h the hash value of 推广计划和推广单元the relevant bucket * @param k the key of interest * @return associate value (or null, if no such entry)

*/protectedabstractVbucketGet(inth,Kk);/** * Associates key k with value v in bucket with hash value h, returning

* the previously associated value, if any. * @param推广计划和推广单元 h the hash value of the relevant bucket * @param k the key of interest

* @param v the value to be associated * @return previous value associated with k (or null, if no such entry)

*/protectedabstractVbucketPut(inth,Kk,Vv);/** * Removes entry having key k from bucket with hash 推广计划和推广单元value h, returning

* the previously associated value, if found. * @param h the hash value of the relevant bucket

* @param k the key of interest * @return previous value associated with k (or null, if no such entry)

*/protectedabstractVbucketRemove(inth,Kk);}好了我觉得我这个周末学不动了....java学起来真难..推广计划和推广单元.