这种映射的好处就是可以把查找的时间复杂度降低到一个常数的水平。常用的一种哈希的实现方式就是使用一个链表的数组。由key对表长取模得到数组的下标。当然下标很可能会产生冲突。解决冲突的办法有很多。这里我们使用的是链地址法。也就是如果下标是相同的,我们就加到数组下标对应的链表中。
- package com.cbs.hash;
- /**
- * 定义哈希表的每一个节点
- * @author CBS
- *
- */
- public class Node < K,
- V > {
- K key; //key值
- V value; //value值
- Node < K,
- V > next; //下一个节点
- public Node() {
- }
- public Node(K k, V v) {
- this.key = k;
- this.value = v;
- }
- }
- package com.cbs.hash;
- /**
- * 自定义哈希表
- * @author CBS
- *
- */
- public class MyHashTable < K,
- V > {
- private Node < K,
- V > [] table;
- private int count = 0; //哈希表长度
- private final float f = 0.75f; //装载因子
- private int index; //数组下标
- private int hash; //哈希值
- //初始化数组长度
- @SuppressWarnings("unchecked") public MyHashTable() {
- table = new Node[9];
- }
- /**
- * 添加方法
- * @param key
- * @param value
- */
- public void put(K key, V value) {
- hash = key.hashCode(); //获取哈希值
- index = (hash & 0x7FFFFFFF) % table.length; //获取下标值
- Node < K,
- V > node = table[index];
- Node < K,
- V > tem = node;
- //如果节点已经存在,更新value值
- for (; tem != null; tem = tem.next) {
- if (hash == tem.key.hashCode() && tem.key.equals(key)) {
- tem.value = value;
- return;
- }
- }
- Node < K,
- V > newNode = new Node < K,
- V > (key, value);
- //在链表的表头插入
- table[index] = newNode;
- newNode.next = node;
- count++;
- }
- /**
- * 查找指定key值下的节点
- * @param k
- * @return key值对应的节点对象
- */
- public Node < K,
- V > find(K k) {
- hash = k.hashCode();
- int index = (hash & 0x7FFFFFFF) % table.length;
- Node < K,
- V > node = table[index];
- Node < K,
- V > tem = node;
- for (; tem != null; tem = tem.next) {
- if (hash == tem.key.hashCode() && tem.key.equals(k)) {
- return tem;
- }
- }
- return null;
- }
- /**
- * 更新key值对应的value值
- * @param k
- * @param v
- */
- public void update(K k, V v) {
- Node < K,
- V > node = find(k);
- node.value = v;
- }
- /**
- * 删除指定key值的节点
- * @param k
- */
- public void delete(K k) {
- hash = k.hashCode();
- int index = (hash & 0x7FFFFFFF) % table.length;
- Node < K,
- V > node = table[index];
- Node < K,
- V > tem = node;
- for (; tem != null; tem = tem.next) {
- if (hash == tem.next.key.hashCode() && tem.next.key.equals(k)) {
- break;
- }
- }
- Node < K,
- V > nextNode = find(k);
- tem.next = nextNode.next;
- count--;
- }
- /**
- * 获取key值节点下面的value值
- * @param k
- * @return V类型的值
- */
- public V get(K k) {
- Node < K,
- V > Node = find(k);
- if (Node != null) {
- return (V) Node.value;
- }
- return null;
- }
- public int size() {
- return count;
- }
- }
来源: http://www.cnblogs.com/cbs-writing/p/7696017.html