Java 里的HashMap(HashTable) 简介.

傷城~ 2022-08-27 12:58 109阅读 0赞

之前已经介绍过Java的另1个容器HashSet.  其实HashMap的存储原来跟HashSet区别不大, 可以说是HashSet的1个扩展.

## 一,预备知识: 哈希表    ##

我们可以把哈希表看做是1个特别的容器.

### 1.1 哈希表的定义    ###

对于1个一般的容器, 无论是List, Queue, 或者Tree, 如果要放入1个新元素(数据), 一般就会放在上1个元素的后1个位置.

也就是说元素在容器的位置跟这个元素本身是无关的.

这些容器实现起来很简单, 但是在容器里查找1个元素, 往往需要遍历容器中的每个位置, 值到找到这个元素.

如果容器的元素足够多, 查找1个元素往往就是1个很耗费成本的行为.

哈希表(Hash Table) 也叫散列表. 如果要放入1个元素, 哈希表会根据这个元素计算出对应的位置. 然后把这个元素放到那个位置中.

如果要查找1个元素, 也是根据这个元素**计算出**(也可以叫映射)对应的位置, 就直接找到了, 不须遍历容器.

也就是说哈希表内的元素的存放位置是由元素本身决定的.

上面的定义只是哈希表的简单概念. 人类还没设计出1个完美的哈希表.

### 1.2 哈希表的优势 ###

根据定义我们就可以看出, 元素的检索速度, 也就是查找性能是哈希表的优势了.

因为哈希表能直接计算出1个元素的位置,  而不需要逐个位置地遍历容器.

### 1.3 哈希表的实现 ###

问题是在编程中如何实现1个哈希表?

首先, 我们需要存放的一个元素提供1个键值(Key),  而且要求两个元素不能具有1个相同的key.

然后哈希表回用1个算法(哈希算法) 根据key计算出1个位置(index).

然后把这个元素放到那个位置中, 如果那个位置已经存在其他元素, 则会被覆盖.

而查找1个元素, 也要这个元素提供一个key, 然后根据哈希算法. 算出这个元素应该放的位置, 然后直接去那个位置访问这个元素.

### 1.4 哈希算法 ###

根据1.3就可以得知, 所谓哈希算法就是根据1个key计算出的元素(value)在哈希表的位置的算法.

不同的哈希表很可能有不同的哈希算法.

哈希算法的实现并不简单, 这个算法的实现要考虑如下几点:

1.计算出的结果(元素存放位置)**必须**在1个范围之内(容器所占的内存范围), 否则 导致超界.

2.根据不同的key(参数)保证得出不同的结果(return value). **这个优先级别比第一点要低**.

所以哈希算法的实现是1个相当复杂的行为, 所幸在java中hash容器已经帮我们写好封装好了.

### 1.5 哈希冲突. ###

一旦哈希算法根据多个不同的key, 返回同1个位置. 这就是哈希冲突了.

有人说这是哈希算法的问题?  实际上因为哈希表的容量和范围所限,几乎所有哈希算法都不能避免哈希冲突.

只能减少哈希冲突发生的几率.

哈希冲突不能避免, 但是能够解决.

加入有2个元素, 它们的key都被映射到相同1个位置, 为了避免其中1个元素覆盖掉另1个元素.

我们可以让那个位置不放置任何元素, 而是放置1个子链表的头部地址, 然后把那两个元素放入到那个子链表中.

如下图:

![444127020140531152959068.png_650x526_130][]

上图每1个子链表里的对象的key都不同, 但是它们的key都映射到同1个位置(哈希冲突).

**带来的缺点就是查找发生哈希冲突的元素还是需要在子链表中遍历.**

### 1.6 哈希因子 ###

假如1个哈希表容器的所占内存(初始容量)是10个单位, 而我们要存放10个元素.

几乎没有哈希算法能根据这个10个元素的key分别指向这个容器的10个不同位置.

只能保证映射的位置在这个哈希表的范围之内. 所以哈希冲突就很可能发生了.

为了尽量减少哈希冲突的几率. 往往我们需要扩大哈希表的容量.

例如我们安排1个具有100个容量单位的哈希表去存放10个元素.  哈希冲突的几率就大大减少了.

假如我们安排1个安排10000个容量单位的哈希表区存放10个元素, 就几乎不存在哈希冲突了. 哈希算法的实现也容易得多.

所以我们把哈希表需要存放的元素个数, 和哈希表所占内存的单位个数的比成为哈希因子.

哈希因子在0与1之间.

如果哈希因子很小, 则代表哈希冲突几率小, 但是很耗费内存空间(很多位置不存放数据)

相反, 如果哈希因子接近1, 则代表哈希冲突的几率很大.

### 1.7 哈希表的缺点 ###

哈希表性能优点在1.2时提到过了, 缺点也很明显, 就是我们为了避免哈希冲突, 往往需要比实际存放的数据更大的空间.

### 1.8 哈希表小结 ###

1.哈希表会根据数据的主键(key)算出数据的存放位置.

2.哈希表主要为了提高数据的存储速度而设计的.

3.哈希表是人类的一种追求, 人类很难设计出完美的哈希表.

4.几乎所有哈希表都回产生哈希冲突.

5.哈希冲突是可以解决的.

## 二,Map接口 ##

我们常常见到在Java中见到HashMap这个容器, 往往有人叫它做哈希图.

实际在编程中, Map不是图的意思, 而是映射.

所以HashMap的中文翻译本屌觉得更应该是"哈希映射".  但是一般叫它左哈希表就ok了.

HashMap和HashTable都实现了Map接口.

![444127020140504232946021.png][]

又上面架构图得知, Map也是1个接口, 但是这个接口没有继承自Collection接口.

因为Map接口不只是存放数据的本身(value), 还需要存放数据提供的主键(Key).

**这种key 和 value的组后就是所谓的键值对(Key-Value), 而Map接口就是为了实现存放键值对的容器而设计的.**

定义如下:

Map保存所谓的'键值对'(Key - Value)信息, 映射中不能出现重复的键(key), 每个键最多只能映射一个值.

## 三,HashMap 和 HashTable简介. ##

实际上HashMap和HashTable都继承了Map接口. 两者都可以被成为"哈希表"

**两者的用法是基本上一样的**, 只不过HashTable里面的方法是同步的(类似于Vector和ArrayList的区别), 而且HashTable不能存放NULL元素.

### 3.1 HashSet的内存存储机制 ###

提到HashMap 不得不提HashSet啊

HashSet可以讲也体现了哈希表的原理.

HashSet是根据元素对象的.hashCode()来作为Key值的.

而是根据equals()方法来比较两个重复的元素. 避免哈希冲突.

如下图:

![444127020140608153706063.png_850x474_130][]

所以放入HashSet的对象必须重写hashCode() 和 equals()方法.

关于HashSet的内存存储机制.

请参考之前的博文,

http://blog.csdn.net/nvd11/article/details/27716511

### 3.1 HashMap的内存存储机制 ###

HashMap的内存机制其实跟HashSet很类似, 可以说HashMap是HashSet的一个扩展.

HashSet: 存储数据本身, 以数据的hashCode()作为Key

HashCode:. 要求数据提供额外的对象作为Key,  先存储Key. 然后再存储对象, 就是存储(key-value)了.

也就是说 **HashCode本身包含1个只存放key对象的1个HashSet**, 这个HashSet内的每个Key再指向1个Value.

![444127020140608155422045.png_966x508_130][]

我们可以看出.

HashMap是以Key对象的hashCode()来计算存储位置,  以key对象的equals()方法来解决哈希冲突.

**所以, 对于HashMap, 数据对象提供的key对象必须重写hashCode()和 equals()方法.**

**建议利用int变量作为key, 因为int变量会被自动装箱成interger变量. 而integer类是已经被重写hashCode()和equals()方法的.**

### 3.1 HashMap的常用方法. ###

#### 3.1.1 Object put(Object key, Object value) ####

Map容器是没有add方法, 相应地提供了put方法来将1个对象放入容器.

1.put方法根据key对象的hashCode()方法计算出存储位置, 如果该位置已有元素, 则覆盖它.

2.而且返回被覆盖的元素对象, 如果之前的位置为空,则返回NULL.

值得记住的就是这个方法的参数, key在前 value在后面.

#### 3.1.2 Object put ALL(Map m) ####

把Map容器m的所有元素加入到当前容器中, 这个方法可能会覆盖多个已有元素.

#### 3.1.3 Object get(Object key) ####

根据提供的key对象返回要获取的数据对象.  如果容器不存在key对应的对象, 则返回NULL..

get()方法和Put()方法是最常用的方法.

#### 3.1.4 int size(); ####

当前容器元素个数.

#### 3.1.5 boolean containsKey(Object key); ####

判断Map容器内是否存在key对象key.

#### 3.1.6 boolean containsValue(Object value); ####

判断Map容器内是否存在对象value. 注意这个方法没有提供key, 所以会导致遍历容器, 不建议使用.

#### 3.1.7 Object remove(Object key); ####

根据提供的key对象在容器中移除对应的键值对, 而且返回被移除的元素对象.

#### 3.1.8 void clear() ####

清空容器..

### 3.2 HashMap的遍历, keySet()方法介绍. ###

如果想遍历HashMap容器的所有元素, 利用循环不不可行的.

但是HashMap提供了1个方法keySet()

它返回1个Set(**注意不是HashSet**), 里面包含了所有key对象的集合.

然后我们利用interator()方法遍历keySet()中的每个key对象, 则可以遍历每个对应的元素对象了.

例子:

import  java.util.HashMap;
    import  java.util.Set;
    import  java.util.Iterator;
    
    class Student{
        int id;
        private String name;
        public Student(int id, String name){
            this.id =  id;
            this.name = name;
        }
    
        public String toString(){
            return this.id + ": " + this.name;
        }
    }
    
    public class HashMap1{
        public static void f(){
            HashMap hm = new HashMap();
            Student st = new Student(1,"Jack");
            hm.put(st.id, st);
            
            st = new Student(2,"Bill");
            hm.put(st.id, st);
    
            st = new Student(3,"Carlos");
            hm.put(st.id, st);
    
            st = new Student(4,"Alice");
            hm.put(st.id, st);
    
            System.out.println(hm.get(4));
    
            //get the HashSet of keys
            Set keyset = hm.keySet();
    
            Iterator it = keyset.iterator();
            while(it.hasNext()){
                st = (Student)hm.get(it.next());    
                System.out.println(st);
            }
    
        }
    }

输出:

[java] 4: Alice
         [java] 1: Jack
         [java] 2: Bill
         [java] 3: Carlos
         [java] 4: Alice

[444127020140531152959068.png_650x526_130]: http://image16.poco.cn/mypoco/myphoto/20140531/15/444127020140531152959068.png?650x526_130
[444127020140504232946021.png]: http://image16.poco.cn/mypoco/myphoto/20140504/23/444127020140504232946021.png
[444127020140608153706063.png_850x474_130]: http://image16.poco.cn/mypoco/myphoto/20140608/15/444127020140608153706063.png?850x474_130
[444127020140608155422045.png_966x508_130]: http://image16.poco.cn/mypoco/myphoto/20140608/15/444127020140608155422045.png?966x508_130