本文目录一览：
java中的Hashtable怎么用，请详细举例子说明，拜托了 谢谢
就是哈希表，下面这个示例创建了一个数字的哈希表。它将数字的名称用作键： HashtableString, Integer numbers = new HashtableString, Integer();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);
要获取一个数字，可以使用以下代码：
Integer n = numbers.get("two");
if (n != null) {
System.out.println("two = " + n);
}
数据结构与算法-基础（十八）哈希表
上期使用 红黑树 实现映射结构，这样的结构满足 Key 必须具备可比性，元素有顺序地分布 这两个特点。在实际的应用场景中，存在结构中的 元素是不需要有序的，并且 Key 也不具备可比较性 ，哈希表完全满足这样的应用场景。
比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 index，员工的名称、职位等作为 value。用哈希表的方式可以将添加、删除和搜索的时间复杂度控制在 O(1)。
这时创建一个数组，手机号作为 index，然后存放 value。这样能将复杂度控制在 O(1)，但是这种 空间换时间 的方式也造成了一些其他问题，比如空间复杂度大（需要更多的空间），空间使用率极其低，非常浪费内存空间。
哈希表 就是空间换时间的处理方式，但是做了优化，在空间和时间两个纬度中达到适当的平衡。
哈希表也叫做散列表，整体结构就是一个数组 ，哈希表会将 key 用哈希函数处理之后返回 hash（哈希值），hash 就是哈希表中的 index这样的处理方式就可以满足搜索时间是 O(1)，这样的处理方式就可以满足搜索时间是 O(1)。因为哈希表中的 key 可能不具备可比较性，所以要做哈希处理。
在执行哈希函数之后返回的 hash，可能会出现相同的情况 ，这样的情况就是 哈希冲突 。解决哈希冲突常见的方法有这三种：
JDK1.8 解决哈希冲突的方式就是使用链地址法，其中的链表就是通过链表+红黑树的组合来实现 。比如当哈希表中的容量大于等于 64，并且单向链表的节点数大于 8 时，转换为红黑树，不满足这个条件时就使用单向链表。
哈希函数 是生成哈希值的实现方法，哈希函数的实现步骤大致分为两步：
hash_code 是生成哈希值的函数，也可以直接用 JAVA 中的标准函数 hashCode() 。
这里可以用 位运算替换 % 运算，来提高效率。因为 位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为 2 的幂次方。
一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。
Key 的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是 尽量让每个 Key 的哈希值唯一，尽量让 Key 中的所有信息参与运算 。
比如在 Java 中， Long 的哈希值实现如下代码：
这里的 和 ^ 就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。
在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 [(j * n + a) * n + c] * n + k，代码实现如下：
看上面代码时，可以发现，表达式中的 n 使用的是 31 这个数字，那么为什么用 31 呢？
因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。
JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：
31 * i = (25 - 1) * i = i * 25 - i = (i 5) - i
数据结构（java版）哈希表的设计
1.什么是哈希表？
哈希表是一种数据结构，它提供了快速的插入操作和查找操作。其基于数组来实现。
2.哈希化
1)直接将关键字作为索引。
2)将单词转换成索引。
1将字母转换成ASCII码，然后进行相加
2幂的连乘
3压缩可选值
3.压缩后仍然可能出现的问题。
冲突：不能保证每个单词都映射到数组的空白单元。
解决办法：
1开放地址法
2链地址法
/**
* 员工信息类
* @author Administrator
*
*/
public class Info {
private String key;
private String name;
public Info(String key, String name) {
this.key = key;
this.name = name;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
import java.math.BigInteger;
public class HashTable {
private Info[] arr;
/**
* 默认的构造方法
*/
public HashTable() {
arr = new Info[100];
}
/**
* 指定数组初始化大小
*/
public HashTable(int maxSize) {
arr = new Info[maxSize];
}
/**
* 插入数据
*/
public void insert(Info info) {
arr[hashCode(info.getKey())] = info;
}
/**
* 查找数据
*/
public Info find(String key) {
return arr[hashCode(key)];
}
public int hashCode(String key) {
// int hashVal = 0;
// for(int i = key.length() - 1; i = 0; i--) {
// int letter = key.charAt(i) - 96;
// hashVal += letter;
// }
// return hashVal;
BigInteger hashVal = new BigInteger("0");
BigInteger pow27 = new BigInteger("1");
for(int i = key.length() - 1; i = 0; i--) {
int letter = key.charAt(i) - 96;
BigInteger letterB = new BigInteger(String.valueOf(letter));
hashVal = hashVal.add(letterB.multiply(pow27));
pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
}
return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
}
}
public class TestHashTable {
public static void main(String[] args) {
HashTable ht = new HashTable();
ht.insert(new Info("a","张三"));
ht.insert(new Info("ct","李四"));
ht.insert(new Info("wangwu","王五"));
System.out.println(ht.find("a").getName());
System.out.println(ht.find("ct").getName());
}
}
