ホームページ Java &#&チュートリアル Java のハッシュ テーブルの詳細な紹介

Java のハッシュ テーブルの詳細な紹介

Nov 29, 2019 pm 04:23 PM
java ハッシュ表

Java のハッシュ テーブルの詳細な紹介

ハッシュ テーブルとは

ハッシュ テーブルは、ハッシュ テーブル (ハッシュ テーブル) とも呼ばれます。 a キーと値の間のマッピング関係を提供するデータ構造。キーが与えられている限り、一致する値を効率的に見つけることができ、時間計算量は O(1) に近くなります。

Java のハッシュ テーブルの詳細な紹介

#オンライン学習ビデオの推奨:

java ビデオ

ハッシュ テーブルの仕組みハッシュ テーブルは本質的には配列です。 a[0]、a[1]、a[2]、a[3]、a[4] などの添字に基づいて配列にランダムにアクセスできることがわかっており、クエリ効率が非常に高くなります。ハッシュ テーブルでは、キーを与えると、対応する値をすぐにクエリできます。このとき、Keyと配列の添字を何らかの方法で変換するための「転送ステーション」が必要になりますが、この転送ステーションがハッシュ関数です。

Java のハッシュ テーブルの詳細な紹介言語が異なれば、ハッシュ関数の実装方法も異なります。 Java で使用されるのは

HashMap

です。 Java およびほとんどのオブジェクト指向言語では、各オブジェクトには、異なるオブジェクトを区別するための独自の

ハッシュコード

があり、このハッシュコードは整数変数です。このとき、この整数変数を配列の添え字に変換する必要がありますが、最も簡単な変換方法は配列の長さの剰余を取ることです。 式は次のとおりです:

index = HashCode(key) % Array.length
ログイン後にコピー

例:

長さ 8 の配列が与えられた場合、キー「001121」に対応する値を見つけたいとします。 、「 001121 のハッシュコード」は 1420036703 である場合、まず次の計算を通じて配列の添字を取得できます。

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7
ログイン後にコピー

ハッシュ テーブルの読み取りおよび書き込み操作

1. 書き込み操作

書き込み操作は、ハッシュ テーブル (jdk では Entry と呼ばれます) に新しいキーと値のペアを挿入することです。

具体的な方法は次のとおりです。ハッシュ関数を使用してキー値を配列添字に変換し、配列内のその位置にエントリを挿入します (単なるエントリ キー値ペアではなく、エントリ キー値のペアであることに注意してください)値)。異なるキー値が同じ添え字に変換され、ハッシュの競合が発生することが考えられます。

ハッシュの競合を解決するために一般的に使用される方法は、オープン アドレス指定方法とリンク リスト方法です。

オープン アドレッシング方式の基本的な考え方は、ハッシュの競合が発生すると、エントリが配列内の次の空の位置に配置される、つまり 1 つずつ戻されるというものです。

リンク リスト メソッド (Java の HashMap コレクション クラスに適用される) の基本的な考え方は、配列内の各要素が Entry オブジェクトであるだけでなく、リンク リストのヘッド ノードでもあるということです。各 Entry オブジェクトは、次のポインタを介して次の Entry ノードを指します。新しい Entry オブジェクトが競合する配列位置にマップされる場合、そのオブジェクトを対応するリンク リストに挿入するだけで済みます。

Java のハッシュ テーブルの詳細な紹介

2. 読み取り操作

読み取り操作は書き込み操作に対応しており、競合状況のみを特別に処理する必要があります。 。

具体的なアイデアは、ハッシュ関数を使用して、検索する Key 値を配列の添字に変換し、配列内のその位置にある Key 値が探している Key であるかどうかを確認するというものです。 Entry の Value 値を返すこともできますが、それ以外の場合は、リンクされたリストの検索を続けて、対応する Key 値があるかどうかを確認します。

たとえば、キー 002936 に対応する値を見つけたい場合、まずキーを配列の添え字に変換し、添え字 2 を取得します。要素を確認すると、要素のキーが 002947 であることがわかります。キーをクエリする場合は、リンクされたリストを下方向に検索し続けます。

Java のハッシュ テーブルの詳細な紹介

3. 拡張

配列内の要素数が最大長に達した場合、配列の拡張が必要であることがわかります。配列 配列を拡張する場合、ハッシュ テーブルはいつ拡張されますか?

複数の要素を挿入した後、ハッシュ テーブルがある程度飽和状態に達すると、配列の同じ添字位置に多数の要素が密集し、ハッシュ競合が発生する可能性が高くなります。ポストオーダーの影響は挿入やクエリのパフォーマンスに大きく影響するため、この際ハッシュテーブルを拡張する必要があります。

ハッシュ テーブルの拡張に影響を与える要因は次のとおりです:

Capacity,即HashMap的当前长度

LoadFactor,即HashMap的负载因子,默认值为0.75

扩容需要满足的条件:

HashMap.Size >= Capacity X LoadFactor
ログイン後にコピー

简单解释为:当哈希表中的条目数超出了当前容量与其加载因子的乘积时,并且要存放的位置已经有元素了(哈希碰撞),这两个条件满足时,需要进项扩容,会将容量扩大为原来的两倍。加载因子默认值0.75,是在空间和时间上的一个折中,加载因子过高(发生冲突可多存放在链表),虽然减少了空间成本,但也增加了查询成本。

扩容的步骤:

扩容不是简单地把散列表的长度扩大,而是经历了下面两个步骤:

1.扩容,创建一个新的Entry空数组,长度时原数组的2倍;

2.重新Hash,遍历原Entry数组,所有的Entry重新Hash到新数组中。

经过扩容,原本拥挤的散列表重新变得稀疏,原有的Entry也重新得到了尽可能均匀的分配。需要注意的是,关于HashMap的实现,JDK8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时,为了提高插入和查找的效率,HashMap会把Entry的链表转化为红黑树这种数据结构。

相关文章教程推荐:java语言入门

以上がJava のハッシュ テーブルの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Javaの平方根 Javaの平方根 Aug 30, 2024 pm 04:26 PM

Java の平方根のガイド。ここでは、Java で平方根がどのように機能するかを、例とそのコード実装をそれぞれ示して説明します。

Javaの完全数 Javaの完全数 Aug 30, 2024 pm 04:28 PM

Java における完全数のガイド。ここでは、定義、Java で完全数を確認する方法、コード実装の例について説明します。

Java の乱数ジェネレーター Java の乱数ジェネレーター Aug 30, 2024 pm 04:27 PM

Java の乱数ジェネレーターのガイド。ここでは、Java の関数について例を挙げて説明し、2 つの異なるジェネレーターについて例を挙げて説明します。

ジャワのウェカ ジャワのウェカ Aug 30, 2024 pm 04:28 PM

Java の Weka へのガイド。ここでは、weka java の概要、使い方、プラットフォームの種類、利点について例を交えて説明します。

Javaのアームストロング数 Javaのアームストロング数 Aug 30, 2024 pm 04:26 PM

Java のアームストロング番号に関するガイド。ここでは、Java でのアームストロング数の概要とコードの一部について説明します。

Javaのスミス番号 Javaのスミス番号 Aug 30, 2024 pm 04:28 PM

Java のスミス番号のガイド。ここでは定義、Java でスミス番号を確認する方法について説明します。コード実装の例。

Java Springのインタビューの質問 Java Springのインタビューの質問 Aug 30, 2024 pm 04:29 PM

この記事では、Java Spring の面接で最もよく聞かれる質問とその詳細な回答をまとめました。面接を突破できるように。

Java 8 Stream Foreachから休憩または戻ってきますか? Java 8 Stream Foreachから休憩または戻ってきますか? Feb 07, 2025 pm 12:09 PM

Java 8は、Stream APIを導入し、データ収集を処理する強力で表現力のある方法を提供します。ただし、ストリームを使用する際の一般的な質問は次のとおりです。 従来のループにより、早期の中断やリターンが可能になりますが、StreamのForeachメソッドはこの方法を直接サポートしていません。この記事では、理由を説明し、ストリーム処理システムに早期終了を実装するための代替方法を調査します。 さらに読み取り:JavaストリームAPIの改善 ストリームを理解してください Foreachメソッドは、ストリーム内の各要素で1つの操作を実行する端末操作です。その設計意図はです

See all articles