HastSet, HashMap(一)

前言

之前我们学习C++ STL的时候也学到了set和map这两种数据结构。不过这里两种数据结构的实现似乎完全的不一样。C++中的是使用红黑书来实现的，而Java中的HashSet和HashMap明显是使用Hash这种结构来实现的。其实使用树还是hash在两种语言中都是有实现的。C++中的使用Hash实现的被称为unordered_set和unordered_map，而Java中使用红黑树来实现的被称为TreeSet和TreeMap。说实话C++中的这种起名方式是真的难听，而且不直观，他用的是是否有序来命令，Java中是使用底层的结构来命名。Java中使用TreeSet/Map其实是比较少的，因为如果要将一中数据放进去，那么这个类必须要实现排序的接口——Comparable。

Hash是什么？

红黑树是什么玩意，这里我们就不详细的去了解了。但是如果连Hash都不知道的话，那么是没办法明白HashMap的。不过我们还是从HashSet开始说起。众所周知Set这个数据结构的要求是无序的，而且是不可以重复的。我们之前学过的存储结构有数组和链表。我们是否可以像ArrayList那样使一个数组来实现Set这个结构呢？当然是可以的。我们可以按顺序放，每次放入新的元素的时候就和前面的所有的元素比较一下。当我们放入了一万个元素的时候，需要和前面的一万个元素进行比较。这种效率简直是无与伦比的垃圾。如果是使用链表呢？？emm，，我想这个时候效率可能是更加的垃圾了。

那么该怎么办呢？

不如来类比一下现实中的例子。假设我们的文件夹中有一万首歌，现在我们需要找一首歌的名字是《青花瓷》。按寻常的方法来做，那就是一首歌一首歌的找。(我为什么不能直接搜索呢？。。你搜索也就以电脑给你一个一个找的啊)。但是我们知道了这首歌是周杰伦的歌。如果我们存放歌曲的时候都按照歌手放一个文件夹的话，我们就可以直接进入到周杰伦的文件夹中去寻找，此时文件夹中歌曲的数目肯定是大大减小了，我们就可以更快的找到我们需要的歌曲了。(你怎么知道歌曲的歌手的？？因为歌曲名和歌手之前存在一种映射。。这里不考虑同名的歌多人唱的情况)。其实也很容易理解，我们讲放在书架上的书有序的排列，那么我们下次想要找到所需要的书的时候就会更加的简单。

不过如何将上面分类的思路运用到数据结构上面来呢？也就是说我们应该用什么样的标准来将数据进行分类呢？

现在我们假设用一个长度为8的数组，需要将数据有顺序的放入这八个数组中。要用什么样的标准呢？上面我们提高了一个非常重要的点——歌曲名和歌手是一一对应的，我们知道了歌曲名那么就可以知道歌手。如果不是一一对应的，我们到底该去哪一个文件夹中去寻找呢？不过数据应该和什么类型的东西对应呢？很容易想到——整型。如果一个数据可以和一个整型相对应。也就是通过一个方法可以将一个类变成一串整型数据，那就搞定了。这个方法正是我们之前说过的hashCode方法。假如说对象A对应的整型是17。我们可以通过最简单的取模的算法（HashSet中肯定不是这么简单）将这个对象A放入数组的一号位。如果遇到了对象B对应的整型是20，但是二号位中没有数据，那么就直接落座。不过又来了个对象C对应的整型是9，它也应该放在一号位上，但是一号位已经是有A对象了的。那么该怎么办呢？这时候就需要比较一下他们对应的整型了。发现一个是17，另一个是9，不相等。那么C就直接挂在A的后面？通过什么方式？？当然是通过链表的方式啦。现在假如又来了个对象D对应的整型也是17。A和D对应的整型是相等的，但是他们自身不想等。这是不矛盾的。产生整型的算法只需要是函数那样，一个x又一个对应的y，但是一个y可能有好几个对应的x。此时和A比较发现对应的整型相等，此时还需要调用equals方法，如果这个方法还是返回true，那么就将D丢掉。如果是false，那么D就开始和链表中的下一个C进行比较。

通过上面的方式，我们实际上就构建出来一个哈希表，也就是经常说的散列。这个哈希表的样子是，一个数组中每一个元素都是一个链表，可以说这个结构是我们之前学的数组和链表的结合体。至于为什么叫散列，其实也是比较直观的，每一列都是不相连的。

使用散列的时候，每次我们想要插入一个数据的时候，首先是通过散列函数计算出他对应的整型，然后通过特定的算法计算出他所在的列。然后通过上满详细说的那种方式，选择插入还是放弃该数据。效率是提高了，但是使用的空间也更多了。

再次需要注意的是，如果两个对象的时候，也就是equals返回false的时候，hashCode方法返回的值必须都要是相等的。但是hashCode相等的时候，两个对象不一定是相等的。至于上面的规则是谁来实现的？那当然不是Java编译器来替我们时间，我们需要重写equals和hashCode方法来保证实现。之前说过的equals ==的时候也讲过了这个东西。

HashSet、HashMap

其实，HashSet这个东西也是非常的少用的。我们这里主要说的还是HashMap，如果HashMap懂了，那么HashSet自然也就懂了。至于为什么呢？请看下面的代码。

/**
 * Constructs a new, empty set; the backing {@code HashMap} instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

可以看到HashSet里面使用就是一个HashMap来实现的，那么我们就直接看一下HashMap就行了。

HashMap的声明

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

public abstract class AbstractMap<K,V>
extends Object
implements Map<K,V>

上面的Cloneable和Serializable这两个接口，我们之前都是已经说过了的。至于父类AbstractMap这个类都是没有那么重要的，这个类只是提供了Map接口的骨架实现，以尽量减少实现此接口所需的工作量。

那么最重要的就是Map<K, V>这个接口。

void clear() 
从该地图中删除所有的映射（可选操作）。  
boolean containsKey(Object key) 
如果此映射包含指定键的映射，则返回 true 。  
boolean containsValue(Object value) 
如果此地图将一个或多个键映射到指定的值，则返回 true 。  
Set<Map.Entry<K,V>> entrySet() 
返回此地图中包含的映射的Set视图。  
boolean equals(Object o) 
将指定的对象与此映射进行比较以获得相等性。  
V get(Object key) 
返回到指定键所映射的值，或 null如果此映射包含该键的映射。   
int hashCode() 
返回此地图的哈希码值。  
boolean isEmpty() 
如果此地图不包含键值映射，则返回 true 。  
Set<K> keySet() 
返回此地图中包含的键的Set视图。  
V put(K key, V value) 
将指定的值与该映射中的指定键相关联（可选操作）。  
void putAll(Map<? extends K,? extends V> m) 
将指定地图的所有映射复制到此映射（可选操作）。  
V remove(Object key) 
如果存在（从可选的操作），从该地图中删除一个键的映射。  
int size() 
返回此地图中键值映射的数量。  
Collection<V> values() 
返回此地图中包含的值的Collection视图。

上面是Map中的抽象方法。其中Map中还有一个接口Entry，这是一个重要的接口。

boolean equals(Object o) 
将指定的对象与此条目进行比较以获得相等性。  
K getKey() 
返回与此条目相对应的键。  
V getValue() 
返回与此条目相对应的值。  
int hashCode() 
返回此映射条目的哈希码值。  
V setValue(V value) 
用指定的值替换与该条目相对应的值（可选操作）。

其中，我们使用entrySet可以返回Map中的键值对，返回的是Set<Map.Entry<K, V>类型。可以使用getKey，getValue方法获取键值对。

总结

上面是对Hash做了一个初步的了解，下面就开始稍微看一下HashMap的源码吧。

赏

一枚小菜鸡