java - 如何降低“put”函数的时间复杂度
问题描述
我试图找到一种方法来让我的算法执行得更快。这个函数目前正在做的是将值(字符)和键(字符串)插入到我的带有 7 个插槽的哈希表中。它还在运行检查 A. 是否有东西占用它的最佳位置,然后将其放置在最佳可用位置。和 B. 如果插入 2 个相同的密钥,则新密钥只是将其值转移到旧密钥,而不是自己占用一个新插槽。有没有办法在不迭代我的“keys”数组的情况下做到这一点?
public void put(String key, Character val) {
int z = hash(key);
while(keys[z] != null){
if(key.equals(keys[z])){
vals[z]= val;
break;
}
z ++;
if (z>6){
z=0;
if(key.equals(keys[z])){
vals[z]= val;
break;
}
if(keys[0]==null){
break;
}
else{
z++;
}
}
}
keys[z] = key;
vals[z] = val;
N += 1;
}
更新:这是我的 hash() 函数
public int hash(String key) {
int i;
int v = 0;
for (i = 0; i < key.length(); i++) {
v += key.charAt(i);
}
return v % M;
}
解决方案
如果我正确理解您的代码,那么您就有一个带有线性探测的开放寻址哈希表。
线性探测的替代方案(您正在搜索空白点的循环)是:
但无论如何,最坏情况下的时间将是线性的。对于一个只有 7 个元素的非常小的表格,您以 1 为增量的线性方法看起来很好。
推荐阅读
- c# - C# 检测最大值并列出所有获取的元素
- php - $file->isValid() 在 laravel 4.2 中返回 false
- javascript - 防止在使用 ajax 分页导航时将上一页 CSS 应用到下一页
- objective-c - FSEventStreamCreateRelativeToDevice:如何获取 deviceID 的根文件夹?
- c# - 如何解决“已经有一个打开的数据阅读器与此连接关联”
- python - SQLAlchemy:禁用延迟加载并仅在 join() 上加载对象
- behat - 如何在 Behat / Mink 中从测试用例/场景中分离数据
- python - 不明白这个“SQL 语句没有足够的参数”错误
- paypal - 如何解释贝宝账单协议的创建?
- html - 如何在 Bootstrap 3 中设置 DIV 的响应高度我的代码附加?