数据结构---散列表

in 数据结构 with 0 comment

散列表是最有用的数据结构之一,,也被称为散列映射、映射、字典和关联数组。在平均情况下,散列表的查找(获取给定索引处的值)速度和数组一样快,插入和删除速度和链表一样快,兼具两者的优点。在最糟糕的情况下,散列表的所有操作的运行时间都为O(n),线性时间。

column1散列表(平均情况)散列表(最糟糕的情况)数组链表
查找O(1)O(n)O(1)O(n)
插入O(1)O(n)O(n)O(1)
查找O(1)O(n)O(n)O(1)

散列表

有家水果店,售卖苹果5元、橘子4元、香蕉6元、菠萝10元...这些水果价格都被记录在本子上。

String[] fruits = {"苹果5元","橘子4元","香蕉6元","菠萝10元"};

如果要查找苹果的价格,不使用任何方法。

	for (int i = 0; i < fruits.length; i++) {
            if (fruits[i].contains("苹果")) {
                System.out.println(fruits[i]);
                break;
            }
        }

需要遍历整个数组,时间复杂度是O(n)。
如果本子内容是按某个顺序排序的,那么可以使用二分查找来找出苹果的价格,时间复杂度是O(logn)。
实际上在记水果价格我们一般是以k:v对的方式来记。

苹果:5元
橘子:4元
香蕉:6元
菠萝:10元
Node{
    String fruit;
    int price;
}
Node[] fruits = {new Node("苹果",5),new Node("橘子",4),
		 new Node("香蕉",6),new Node("菠萝",10)};

数组的查找时间的复杂度是O(1),如果能通过某个方法,可以找到橘子在数组的第几位,那通过数组的特性,一次性就可以知道了橘子的价格。这个方法就是散列表的散列函数了。

散列函数

散列函数简单点说,无论你给它什么数据,它都返回给你一个数字。即将输入映射到数字。
散列函数必须要满足以下要求:

  1. 必须是一致的。比如输入苹果,得到的4,那么每次输入苹果,得到的必须是4.
  2. 应将不同的输入映射到不同的数字。如果一个散列表不管输入的是什么都返回1,它就不是好的散列函数。最理想的情况是将不同的输入映射到不同的数字。
F(苹果)=4,将苹果的价格放在数组的第4位
F(橘子)=2,将橘子的价格放在数组的第2位
F(香蕉)=1,将香蕉的价格放在数组的第1位
F(菠萝)=3,将菠萝的价格放在数组的第3位

如果再去查找苹果的价格

F(苹果)=4,苹果的位置在数组的第4位,查找fruits[4].price=5

散列函数准确的指出了苹果的存储位置,不需要再去简单查找,时间复杂度是O(1)。
结合散列函数和数组就创建了名为散列表的数据结构了。

散列表的使用场景

  1. 因为存储的是k:v对,所以散列表模拟映射关系。
  2. 散列表的k是不能重复的,所以散列表可以防止重复。
  3. 在查找方面散列表很快,所以散列表很适合做缓存,避免服务器再处理数据。比如域名:Ip地址。

散列冲突

现在水果店又进货了西瓜。

F(西瓜)=4

第四号位置已经存储了苹果的价格,这种情况就称为冲突,如果将西瓜的价格存储在这个位置那么就会覆盖苹果的价格,以后再找苹果的价格得到的就是西瓜的价格了。必须要处理冲突。

均匀的哈希函数可以减少冲突,但不能避免冲突。发生冲突后,必须解决;也即必须寻找下一个可用地址。

开放寻址法

如果西瓜的散列函数值和苹果一样,且苹果已经存储了,就往下一个找(比如+1),直到F(key)中没有值了,就放进去。

F(西瓜)=4 苹果存在了,下一位,第5号位空,西瓜放在第5号位
F(猕猴桃)=4 苹果存在了,下一位,西瓜存在了,下一位,第6号位空,猕猴桃第6号位

分为线性探测再散列、二次探测再散列、伪随机探测再散列。

再散列法

准备多个散列函数

F(n)
H(n)
G(n)

产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。

链地址法

散列表采用数组加链表的方式实现。如果苹果、西瓜、猕猴桃散列函数的结果相同。通过链表的方式存储这三条数据。

fruits[4] = 苹果->西瓜->猕猴桃

散列函数的性能

在平均情况下,散列表查找速度和数组一样快。
查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:

  1. 散列函数是否均匀:输入的元素都均匀的分布在散列表上。
  2. 处理冲突的方法:链地址法会导致在链表上查找,链表查询的时间复杂度是O(n)
  3. 散列表的装填因子:装满程度的标志因子。由于表长是定值,装填因子与“填入表中的元素个数”成正比,所以,装填因子越大,填入表中的元素较多,产生冲突的可能性就越大;装填因子越小,填入表中的元素较少,产生冲突的可能性就越小。一旦装填因子超过0.7就该调整散列表的长度了
装填因子=散列表包含的元素个数/位置总数

哈希表的构造方法

  1. 直接定址法
  2. 数字分析法
  3. 平方取中法
  4. 折叠法
  5. 除留余数法
  6. 随机数法

自己做一个散列表

  1. 使用链地址法,需要先定义一个链表。
class PLNode {
        int hash; //散列值
        String key; //key
        Integer value; //value
        PLNode next; //链表的next
}
  1. 散链表的数组。
// 数组
PLNode[] table;
  1. 使用取余法作为散列函数
// 计算key的哈希值
int h = hash(key);
// 获得桶的位置
int index = h % table.length;

// hash算法,通过高低16位来重新hashcode
// key计算出来的hashCode()只有高位变化时,最终算出来的index索引就会引起hash冲突
// 如果冲突太多的话HashMap的效率就会非常低下了
int hash(String key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4.插入元素

public Integer putPlMap(String key, Integer value) {
        // 计算key的哈希值
        int h = hash(key);
        // 获得桶的位置
        int index = h % table.length;
        // 如果第一个位置为null
        if (table[index] == null) {
            table[index] = new PLNode(h, key, value, null);
        } else {
            // 遍历,找到该在的链表位置
            PLNode e;
            PLNode p = table[index];
            while (true) {
                e = p;
                if (e != null && p.key.equals(key)) {
                    p.value = value;
                    break;
                }
                if ((e = p.next) == null) {
                    p.next = new PLNode(h, key, value, null);
                    break;
                }
                p = e;
            }
        }
        return value;
    }
  1. 获得元素
// 获得值
    Integer get(String key) {
        PLNode first, e;
        int h = hash(key);
        // 获得桶的位置
        int index = h % table.length;
        first = table[index];
        if ((e = first) != null) {
            if (first.hash == h) return first.value;
        } else {
            do {
                e = e.next;
                if (e.hash == h) return first.value;
            } while (e.next != null);
        }
        return null;
    }
  1. 测试
public static void main(String[] args) {
        String[] keys = {"苹果", "橘子", "香蕉", "菠萝"};
        Integer[] values = {5, 4, 6, 10};
        PLMap map = new PLMap(8);
        for (int i = 0; i < keys.length; i++) {
            map.putPlMap(keys[i], values[i]);
        }
        System.out.println("价格为:"+map.get("橘子"));
        map.putPlMap("橘子", 7);
        System.out.println("修改后价格为:"+map.get("橘子"));
}

运行结果
image.png

总结

主要是为了再次熟悉数据结构的一些手写操作,然后写的玩玩。
装填因子的作用可以看HashMap的源码,之前有写过源码。

学习来源:《算法图解》《百度百科》JDK源码HashMap