赞
踩
散列函数(Hash Function),也称为哈希函数或哈希算法,是一种将任意大小的数据转换成固定大小的值的函数。这个转换后的值通常被称为哈希值或哈希码。散列函数在计算机科学中有着广泛的应用,尤其是在数据检索、加密和数据结构(如哈希表)等领域。
public class SimpleHashFunction { public static int hash(String key, int arraySize) { int hashValue = 0; for (int i = 0; i < key.length(); i++) { hashValue = (hashValue << 5) - hashValue + key.charAt(i); hashValue |= 0; // Convert to 32bit positive value } return Math.abs(hashValue) % arraySize; } public static void main(String[] args) { String key = "Kimi"; int arraySize = 10; int hashValue = hash(key, arraySize); System.out.println("Hash value for '" + key + "': " + hashValue); } }
在面试中,了解散列函数的原理和应用是非常重要的。面试官可能会询问你关于散列函数的设计原则、碰撞处理方法、以及不同散列函数的优缺点。希望这些知识点和示例代码能够帮助你更好地准备面试!
描述:
设计一个哈希表,包括初始化、插入、删除和查找操作,并确保哈希表在处理大量数据时具有高效的性能。
示例:
哈希表的初始大小为 10,支持插入 key-value 对、删除指定的 key、查找指定的 key,以及返回哈希表的大小。
Java 源码:
public class HashTable { static class Entry { int key; String value; Entry next; Entry(int key, String value) { this.key = key; this.value = value; this.next = null; } } private static final int INIT_CAPACITY = 10; private Entry[] buckets; private int size; public HashTable() { buckets = new Entry[INIT_CAPACITY]; size = 0; } public void put(int key, String value) { int index = hash(key); Entry entry = new Entry(key, value); if (buckets[index] == null) { buckets[index] = entry; } else { buckets[index] = addEntry(buckets[index], entry); } size++; } public void remove(int key) { int index = hash(key); if (buckets[index] != null) { buckets[index] = removeEntry(buckets[index], key); } } public String get(int key) { int index = hash(key); Entry entry = buckets[index]; while (entry != null) { if (entry.key == key) { return entry.value; } entry = entry.next; } return null; } public int getSize() { return size; } private int hash(int key) { return Math.abs(key % buckets.length); } private Entry addEntry(Entry head, Entry entry) { if (head == null) { return entry; } Entry current = head; while (current.next != null) { if (current.next.key == entry.key) { current.next.value = entry.value; return head; } current = current.next; } current.next = entry; return head; } private Entry removeEntry(Entry head, int key) { if (head == null) { return null; } if (head.key == key) { Entry result = head.next; head.next = null; return result; } Entry current = head; while (current.next != null) { if (current.next.key == key) { Entry toDelete = current.next; current.next = current.next.next; return toDelete; } current = current.next; } return head; } public static void main(String[] args) { HashTable table = new HashTable(); table.put(1, "one"); table.put(2, "two"); table.put(3, "three"); System.out.println("Hash table size: " + table.getSize()); System.out.println("Value for key 2: " + table.get(2)); table.remove(2); System.out.println("Value for key 2 after removal: " + table.get(2)); } }
描述:
实现一个解决散列冲突的链地址法(Chaining)哈希表,并提供插入和查找操作。
示例:
插入 key-value 对 (1, "a") 和 (1, "b"),查找 key 为 1 的所有值。
Java 源码:
public class ChainingHashTable { private static class Entry { int key; String value; Entry next; Entry(int key, String value) { this.key = key; this.value = value; this.next = null; } } private Entry[] table; private int size; public ChainingHashTable(int capacity) { table = new Entry[capacity]; size = 0; } public void insert(int key, String value) { int index = hash(key); Entry newEntry = new Entry(key, value); if (table[index] == null) { table[index] = newEntry; } else { Entry current = table[index]; while (current.next != null) { if (current.key == key) { current.value = value; // Update existing key return; } current = current.next; } current.next = newEntry; } size++; } public String search(int key) { int index = hash(key); Entry entry = table[index]; while (entry != null) { if (entry.key == key) { return entry.value; } entry = entry.next; } return null; } private int hash(int key) { return Math.abs(key % table.length); } public static void main(String[] args) { ChainingHashTable table = new ChainingHashTable(10); table.insert(1, "a"); table.insert(1, "b"); System.out.println("Value for key 1: " + table.search(1)); } }
描述:
实现一个简单的散列函数,计算字符串的哈希值,并处理散列冲突。
示例:
输入字符串 "hello",输出其哈希值。
Java 源码:
public class SimpleStringHash { public int hash(String s) { int hashValue = 0; int prime = 31; // 使用一个质数作为乘数 for (int i = 0; i < s.length(); i++) { hashValue = (hashValue * prime) + s.charAt(i); } return Math.abs(hashValue) % 100; // 取绝对值并限制哈希值的范围 } public static void main(String[] args) { SimpleStringHash hash = new SimpleStringHash(); int hashValue = hash.hash("hello"); System.out.println("Hash value for 'hello': " + hashValue); } }
这些题目和源码展示了散列函数在不同场景下的应用。在面试中,能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。