- 使用 Spring Initializr 创建 Spring Boot 应用程序
- 在Spring Boot中配置Cassandra
- 在 Spring Boot 上配置 Tomcat 连接池
- 将Camel消息路由到嵌入WildFly的Artemis上
顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN),搜索的效率取决于搜索过程中
元素的比较次数。
理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系, 那么在查找时通过该函数可以很快找到该元素
当向该结构中:
该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(HashTable)(或者称散列表)
例如: 数据集合{1,7,6,4,5,9};
哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小
用该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快
问题: 按照上述哈希方式,向集合中插入元素44,会出现什么问题?
不同关键字 通过 相同哈希函数 计算出 相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”
首先,我们需要明确一点,由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的,这就导致一个问题,冲突的发生是必然的,但我们能做的应该是尽量的降低冲突率。
引起哈希冲突的一个原因可能是:哈希函数设计不够合理。 哈希函数设计原则:
常见哈希函数
取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B
面试题:
Leet 387: 字符串中的第一个唯一字符
描述: 给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 。如果不存在,则返回 -1 。
解题思路:
arr
长度为 26ch
, 让 arr[ch-'a']++;
ch
,判断arr[ch-'a'] == 1
,代码实现:
class Solution {
public int firstUniqChar(String s) {
int[] arr = new int[26];
for(Character ch : s.toCharArray()){
arr[ch-'a'] ++;
}
for (int i = 0; i < s.length(); i++) {
if(arr[s.charAt(i)-'a']==1){
return i;
}
}
return -1;
}
}
设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数,按照哈希函数:Hash(key) = key% p(p<=m)
,将关键码转换成哈希地址
假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散列地址。例如:
假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是 相同的,那么我们可以选择后面的四位作为散列地址,如果这样的抽取工作还容易出现 冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况,如果事先知道关键字的分布且关键字的若干位分布较均匀的情况
注意:哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突
散列表的载荷因子定义为: α = 填入表中的元素个数 / 散列表的长度
α是散列表装满长度的标志因子.由于表长是定值.α与"填入表中的元素个数"成正比,所以,α越大,表明填入表中的元素越多,产生冲突的可能性就越大;反之,α越小,标明填入表中的元素越少,产生冲突的可能性就越小.实际上,散列表的平均查找长度是负载因子α的函数,只是不同处理冲突的方法有不同的函数.
对于开放定址法,负载因子是特别重要的因素,应严格限制在0.7~0.8以下,超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升.因此,一些采用开放定址法的hash库,如Java的系统库限制了荷载因子为0.75,超过此值将resize散列表.
负载因子和冲突率的关系粗略演示
所以当冲突率达到一个无法忍受的程度时,我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的,那我们能调整的就只有哈希表中的数组的大小。
闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。
如何寻找空的位置?
比如上面的场景,现在需要插入元素44,先通过哈希函数计算哈希地址,下标为4,因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。
线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。
插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突,使用线性探测找到下一个空位置,插入新元素
采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
缺点: 产生冲突的数据堆积在一块,这与其找下一个空位置有关系,因为找空位置的方式就是挨着往后逐个去找
因此二次探测为了避免该问题,找下一个空位置的方法为: Hi= ( H0+i2 ) % m
其中:i = 1,2,3…, H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置,m是表的大小。
研究表明: 当表的长度为质数且表装载因子a不超过0.5时,新的表项一定能够插入,而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置,就不会存在表满的问题。在搜索时可以不考虑表装满的情况,但在插入时必须确保表的装载因子a不超过0.5,如果超出必须考虑增容
因此:闭散列最大的缺陷就是空间利用率比较低,这也是哈希的缺陷
开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
public class HashBuck {
static class Node {
public int key;
public int val;
public Node next;
public Node(int key,int val) {
this.key = key;
this.val = val;
}
}
public Node[] array;
public int usedSize;
public static final double DEFAULT_LOAD_FACTOR = 0.75;
public HashBuck() {
this.array = new Node[10];
}
public void put(int key,int val){
// 1. 找到key的位置
int index = key % array.length;
// 2. 遍历这个下标的链表,看是否有相同key,有相同的key需要更新val
Node cur = array[index];
while (cur != null){
if(cur.key == key){
cur.val = val;
return;
}
cur = cur.next;
}
//3.没有这个key这个元素
//头插法
/*Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;*/
//尾插法
Node node = new Node(key, val);
if(array[index] == null){
array[index] = node;
}else {
Node tmp = array[index];
while(tmp.next != null){
tmp = tmp.next;
}
tmp.next = node;
}
this.usedSize++;
//4.插入元素成功之后,检查当前散列表的负载因子
if(loadFactor() > DEFAULT_LOAD_FACTOR){
resize();
}
}
private void resize() {
Node[] newArray = new Node[array.length*2];
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null){
int index = cur.key % newArray.length;//获取新的下标
// cur节点以头插或尾插形式 插入到新的数组对应下标的链表当中
Node curNext = cur.next;
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
array = newArray;
}
private double loadFactor() {
return 1.0 * usedSize / array.length;
}
/**
* 根据key获取val的值
* @param key
* @return
*/
public int get(int key){
int index = key % array.length;
Node cur = array[index];
while (cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}
}
class Person {
public String ID;
public Person(String ID) {
this.ID = ID;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
return Objects.equals(ID, person.ID);
}
@Override
public int hashCode() {
return Objects.hash(ID);
}
@Override
public String toString() {
return "Person{" +
"ID='" + ID + '\'' +
'}';
}
}
public class HashBuck<K,V> {
static class Node<K,V> {
public K key;
public V val;
public Node<K,V> next;
public Node(K key,V val) {
this.key = key;
this.val = val;
}
}
public Node<K,V>[] array = (Node<K, V>[]) new Node[10];
public int usedSize;
public void put(K key,V val){
int index = key.hashCode() % array.length;
Node<K,V> cur = array[index];
while (cur != null){
if(cur.key.equals(key)){
cur.val = val;
return;
}
cur = cur.next;
}
Node<K,V> node = new Node<>(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
}
public V get(K key){
int index = key.hashCode() % array.length;
Node<K,V> cur = array[index];
while (cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return null;
}
}
虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突个数是可控的,也就是每个桶中的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入/删除/查找时间复杂度是
O(1) 。
注意事项:
我目前正在尝试基于哈希表构建字典。逻辑是:有一个名为 HashTable 的结构,其中包含以下内容: HashFunc HashFunc; PrintFunc PrintEntry; CompareF
如果我有一个指向结构/对象的指针,并且该结构/对象包含另外两个指向其他对象的指针,并且我想删除“包含这两个指针的对象而不破坏它所持有的指针”——我该怎么做这样做吗? 指向对象 A 的指针(包含指向对象
像这样的代码 package main import "fmt" type Hello struct { ID int Raw string } type World []*Hell
我有一个采用以下格式的 CSV: Module, Topic, Sub-topic 它需要能够导入到具有以下格式的 MySQL 数据库中: CREATE TABLE `modules` ( `id
通常我使用类似的东西 copy((uint8_t*)&POD, (uint8_t*)(&POD + 1 ), back_inserter(rawData)); copy((uint8_t*)&PODV
错误 : 联合只能在具有兼容列类型的表上执行。 结构(层:字符串,skyward_number:字符串,skyward_points:字符串)<> 结构(skyward_number:字符串,层:字符
我有一个指向结构的指针数组,我正在尝试使用它们进行 while 循环。我对如何准确初始化它并不完全有信心,但我一直这样做: Entry *newEntry = malloc(sizeof(Entry)
我正在学习 C,我的问题可能很愚蠢,但我很困惑。在这样的函数中: int afunction(somevariables) { if (someconditions)
我现在正在做一项编程作业,我并没有真正完全掌握链接,因为我们还没有涉及它。但是我觉得我需要它来做我想做的事情,因为数组还不够 我创建了一个结构,如下 struct node { float coef;
给定以下代码片段: #include #include #define MAX_SIZE 15 typedef struct{ int touchdowns; int intercepti
struct contact list[3]; int checknullarray() { for(int x=0;x<10;x++) { if(strlen(con
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Empty “for” loop in Facebook ajax what does AJAX call
我刚刚在反射器中浏览了一个文件,并在结构构造函数中看到了这个: this = new Binder.SyntaxNodeOrToken(); 我以前从未见过该术语。有人能解释一下这个赋值在 C# 中的
我经常使用字符串常量,例如: DICT_KEY1 = 'DICT_KEY1' DICT_KEY2 = 'DICT_KEY2' ... 很多时候我不介意实际的文字是什么,只要它们是独一无二的并且对人类读
我是 C 的新手,我不明白为什么下面的代码不起作用: typedef struct{ uint8_t a; uint8_t* b; } test_struct; test_struct
您能否制作一个行为类似于内置类之一的结构,您可以在其中直接分配值而无需调用属性? 前任: RoundedDouble count; count = 5; 而不是使用 RoundedDouble cou
这是我的代码: #include typedef struct { const char *description; float value; int age; } swag
在创建嵌套列表时,我认为 R 具有对列表元素有用的命名结构。我有一个列表列表,并希望应用包含在任何列表中的每个向量的函数。 lapply这样做但随后剥离了列表的命名结构。我该怎么办 lapply嵌套列
我正在做一个用于学习目的的个人组织者,我从来没有使用过 XML,所以我不确定我的解决方案是否是最好的。这是我附带的 XML 文件的基本结构:
我是新来的 nosql概念,所以当我开始学习时 PouchDB ,我找到了这个转换表。我的困惑是,如何PouchDB如果可以说我有多个表,是否意味着我需要创建多个数据库?因为根据我在 pouchdb
我是一名优秀的程序员,十分优秀!