Java數據結構與算法(散列表)

前言

散列表是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說,它通過把關鍵碼值映射到表中一個位置來訪問記錄,以加快查找的速度。而key的沖突主要通過鏈表的方式來處理,后期鏈表過長情況下可以通過紅黑樹來優化查詢效率。

實現原理

  1. 散列函數(Hash Function): 散列函數用于將輸入的鍵轉換為表中的索引。理想的散列函數應當將鍵均勻地分布到表的各個位置,以減少沖突。散列函數的一些常見實現包括將鍵的ASCII值進行某種數學運算或使用更復雜的算法,如SHA-256。

  2. 沖突(Collision): 當兩個不同的鍵通過散列函數映射到相同的位置時,就會發生沖突。處理沖突是散列表實現中的一個關鍵問題。

動畫過程

Open Hashing Visualization

具體代碼實現

import java.util.LinkedList;public class HashTable<K, V> {// Node class to store key-value pairsprivate static class Node<K, V> {K key;V value;Node(K key, V value) {this.key = key;this.value = value;}}// Default size of the hash tableprivate static final int DEFAULT_SIZE = 16;// Array of linked lists to store the chainsprivate LinkedList<Node<K, V>>[] table;// Current size of the hash tableprivate int size;// Constructor to initialize the hash table with default size@SuppressWarnings("unchecked")public HashTable() {table = new LinkedList[DEFAULT_SIZE];size = 0;}// Hash function to compute index for a keyprivate int hash(K key) {return Math.abs(key.hashCode() % table.length);}// Method to insert a key-value pair into the hash tablepublic void insert(K key, V value) {int index = hash(key);if (table[index] == null) {table[index] = new LinkedList<>();}// Check if the key already exists, update value if it doesfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {node.value = value;return;}}// If key does not exist, add a new node to the chaintable[index].add(new Node<>(key, value));size++;}// Method to retrieve a value by its keypublic V get(K key) {int index = hash(key);if (table[index] == null) {return null;}// Search for the key in the chainfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {return node.value;}}// If key is not found, return nullreturn null;}// Method to delete a key-value pair from the hash tablepublic boolean delete(K key) {int index = hash(key);if (table[index] == null) {return false;}// Search for the key in the chain and remove itfor (Node<K, V> node : table[index]) {if (node.key.equals(key)) {table[index].remove(node);size--;return true;}}return false;}// Method to get the current size of the hash tablepublic int size() {return size;}// Method to check if the hash table is emptypublic boolean isEmpty() {return size == 0;}// Main method for testingpublic static void main(String[] args) {HashTable<String, Integer> hashTable = new HashTable<>();hashTable.insert("apple", 1);hashTable.insert("banana", 2);hashTable.insert("cherry", 3);System.out.println("Value for 'apple': " + hashTable.get("apple"));System.out.println("Value for 'banana': " + hashTable.get("banana"));System.out.println("Value for 'cherry': " + hashTable.get("cherry"));hashTable.delete("banana");System.out.println("Value for 'banana' after deletion: " + hashTable.get("banana"));System.out.println("Current size: " + hashTable.size());}
}

QA:待定

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/18111.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/18111.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/18111.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

進程互斥經典問題(讀寫者問題、理發店問題)

目錄 讀寫者問題 問題描述 問題分析 進程互斥問題三部曲 讀者寫者算法實現 一、找進程——確定進程關系 二、找主營業務 三、找同步約束 a.互斥 b.資源 c.配額 理發店問題 問題描述 問題分析 進程互斥問題三部曲 理發店問題算法實現 一、找進程——確定進程…

SB-OSC,最新的 MySQL Schema 在線變更方案

目前主流的 MySQL 在線變更方案有兩個&#xff1a; 基于 trigger 的 pt-online-schema-change基于 binlog 的 gh-ost 上周 Sendbird 剛開源了他們的 MySQL Schema 在線變更方案 SB-OSC: Sendbird Online Schema Change。 GitHub 上剛剛 25 顆星星&#xff0c;絕對新鮮出爐。 …

Qt Creator(2)【如何在Qt Creator中創建新工程】

閱讀導航 引言一、Qt Creator開始界面介紹二、如何在Qt Creator中創建新工程1. 新建項目2. 選擇項目模板3. 選擇項目路徑4. 選擇構建系統5. 填寫類信息設置界面6. 選擇語言和翻譯文件7. 選擇Qt套件8. 選擇版本控制系統9. 最終效果 三、認識Qt Creator項目內容界面1. 基本界面2.…

React Native 之 處理觸摸事件(八)

React Native 提供了可以處理常見觸摸手勢&#xff08;例如點擊或滑動&#xff09;的組件&#xff0c; 以及可用于識別更復雜的手勢的完整的手勢響應系統。 Button是一個簡單的跨平臺的按鈕組件。下面是一個最簡示例&#xff1a; <ButtononPress{() > {Alert.alert(你點…

go語言初識別(五)

本博客內容涉及到&#xff1a;切片 切片 1. 切片的概念 首先先對數組進行一下回顧&#xff1a; 數組定義完&#xff0c;長度是固定的&#xff0c;例如&#xff1a; var num [5]int [5]int{1,2,3,4,5}定義的num數組長度是5&#xff0c;表示只能存儲5個整形數字&#xff0c…

檢索模型預訓練方法:RetroMAE

論文title&#xff1a;https://arxiv.org/pdf/2205.12035RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder 論文鏈接&#xff1a;https://arxiv.org/pdf/2205.12035 摘要 1.一種新的MAE工作流&#xff0c;編碼器和解器輸入進行了不同的掩…

華為OD機試【計算最接近的數】(java)(100分)

1、題目描述 給定一個數組X和正整數K&#xff0c;請找出使表達式X[i] - X[i1] … - X[i K 1]&#xff0c;結果最接近于數組中位數的下標i&#xff0c;如果有多個i滿足條件&#xff0c;請返回最大的i。 其中&#xff0c;數組中位數&#xff1a;長度為N的數組&#xff0c;按照元…

軟件性能測試有哪些測試類型和方法?

軟件性能測試是一種通過模擬真實用戶使用情況&#xff0c;評估軟件系統在各種壓力和負載下的表現的測試方法。在今天這個講究效率的時代&#xff0c;軟件性能測試是不可或缺的一環。它能幫助開發人員和企業發現潛在的性能問題&#xff0c;提前優化改進&#xff0c;保證軟件系統…

Flutter 中的 SizeChangedLayoutNotifier 小部件:全面指南

Flutter 中的 SizeChangedLayoutNotifier 小部件&#xff1a;全面指南 在 Flutter 中&#xff0c;SizeChangedLayoutNotifier 是一種特殊的小部件&#xff0c;它用于監聽其子組件尺寸的變化。當子組件的大小發生變化時&#xff0c;SizeChangedLayoutNotifier 可以通知其他組件…

動態內存管理—C語言通訊錄

目錄 一&#xff0c;動態內存函數的介紹 1.1 malloc和free 1.2 calloc 1.3 realloc 1.4C/C程序的內存開辟 二&#xff0c;通訊錄管理系統 動態內存函數的介紹 malloc free calloc realloc 一&#xff0c;動態內存函數的介紹 1.1 malloc和free void* malloc (…

回文鏈表(快慢指針解法之在推進過程中反轉)

歸納編程學習的感悟&#xff0c; 記錄奮斗路上的點滴&#xff0c; 希望能幫到一樣刻苦的你&#xff01; 如有不足歡迎指正&#xff01; 共同學習交流&#xff01; &#x1f30e;歡迎各位→點贊 &#x1f44d; 收藏? 留言?&#x1f4dd;抱怨深處黑暗&#xff0c;不如提燈前行…

進程間通信IPC機制

進程間通信&#xff08;IPC&#xff0c;InterProcess Communication&#xff09;是指在不同進程之間傳播或交換信息。IPC機制有多種方式&#xff0c;每種方式都有其特定的工作原理、應用場景以及優缺點。以下是對幾種主要IPC方式的詳細解釋&#xff1a; 管道&#xff08;Pipe&a…

數據結構算法題day04

數據結構算法題day04 題目分析算法思想代碼完整運行代碼如下&#xff1a; 題目 對長度為n的順序表L&#xff0c;編寫一個時間復雜度為O(n)、空間復雜度為O(1)的算法 該算法刪除線性表中所有值為X的數據元素。分析 O(n) -> 掃描一次順序表 O(1) -> 申請常數個輔助空間 1…

代碼隨想錄算法訓練營day14|二叉樹的遞歸遍歷、二叉樹的迭代遍歷、二叉樹的統一迭代法

二叉樹的遞歸遍歷 首先需要明確的一點是&#xff0c;前序中序和后序在二叉樹的遞歸遍歷中的區別僅在于遞歸函數中操作的順序&#xff0c;前序是在遍歷一個節點的左右子樹前進行操作&#xff0c;中序是在遍歷一個節點的左子樹后進行操作再遍歷右子樹&#xff0c;而后序是在遍歷…

C++算術運算和自增自減運算

一 引言 表示運算的符號稱為運算符。 算術運算&#xff1b; 比較運算&#xff1b; 邏輯運算&#xff1b; 位運算&#xff1b; 1 算術運算 算術運算包括加、減、乘、除、乘方、指數、對數、三角函數、求余函數&#xff0c;這些都是算術運算。 C中用、-、*、/、%分別表示加、減…

【AI】AI框架項目OpenWebUI如何追加模型

【背景】 openWebUI是一個非常好用的AI框架項目&#xff0c;既可以用API形式連接各類外部AI模型&#xff0c;也可以直接連接服務器硬盤上部署的離線大模型。 簡單來說&#xff0c;OpenWebUI可以用來方便地把你的本地模型變為可供所有內網人員使用的SAAS服務站點&#xff0c;并…

《當微服務遇上Ribbon:一場負載均衡的華麗舞會》

在微服務的廚房里&#xff0c;如何確保每一道服務都恰到好處&#xff1f;揭秘Spring Cloud Ribbon如何像大廚一樣精心調配資源&#xff0c;讓負載均衡變得像烹飪藝術一樣簡單&#xff01; 文章目錄 Spring Cloud Ribbon 詳解1. 引言微服務架構中的負載均衡需求Spring Cloud Rib…

【算法實戰】每日一題:設計一個算法,用最少數量的矩形覆蓋一系列寬度為d、高度為w的矩形,且使用矩形不能超出邊界

題目 設計一個算法&#xff0c;用最少數量的矩形覆蓋一系列寬度為d、高度為w的矩形建筑物側墻&#xff0c;且矩形不能超出邊界。 核心思路 考慮這種結構 前面遞增后面一個與前面的某個高度一致&#xff0c;這時候考慮最下面的覆蓋&#xff08;即都是從最下面向上覆蓋&#…

redis數據類型set,zset

華子目錄 Set結構圖相關命令sdiff key1 [key2]sdiffstore destination key1 [key2...]sinter key1 [key2...]sinterstore destination key1 [key2...]sunion key1 [key2...]sunionstore destination key1 [key2...]smove source destination memberspop key [count]sscan key c…

Java GC問題排查的一些個人總結和問題復盤

個人博客 Java GC問題排查的一些個人總結和問題復盤 | iwts’s blog 是否存在GC問題判斷指標 有的比較明顯&#xff0c;比如發布上線后內存直接就起飛了&#xff0c;這種也是比較好排查的&#xff0c;也是最多的。如果單純從優化角度&#xff0c;看當前應用是否需要優化&…