ハッシュ表のバケット数
1000個のキーを負荷率0.75で収めるには少なくとも1334個のバケットが必要で、2のべき乗に切り上げると2048個になります。実際の負荷率、収まるキーの数、残りの余裕も分かります。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 項目
- 1,000
- 負荷率
- 0.75
- 丸め
- Power of two
- 最小バケット数
- 1,334
- バケット
- 2,048
- 実際の負荷率
- 0.48828125
- 容量
- 1,536
ハッシュ表の速さは、背後の配列が適切に寸法決めされているかどうかに尽きます。n個の鍵をm個のバケットへ入れると、負荷率α = n / mが、鎖の伸び、開放番地法の塊り、再確保の頻度を決めます。mが小さすぎれば、毎回の検索が衝突の山を辿ります。mが大きすぎれば、遅延を助けない空き枠にRAMを払うことになります。このハッシュ表バケット数計算機は、見込まれる要素数、Java HashMapの既定である0.75のような目標負荷率、および丸め方針を受け取り、占有がその目標以下に収まる、割り当て可能な最小の表を返します。まず生の天井ceil(n / α)を求め、その床を次の2の冪または次の素数へ切り上げます。これが本番の対応表が実際に確保する二つの大きさです。2の冪の大きさは、ハッシュと(m引く一)のビット単位ANDで添字を付けるマスク型の対応表に合います。素数の大きさは、hash mod mで添字を付ける剰余型の対応表に合います。
切りの良い当て推量ではなく負荷率がバケット数を決めるべき理由
負荷率は、言語をまたいで通用する唯一の占有数です。Java HashMapの既定は0.75で、大きさが容量にその係数を掛けた値を超えると再確保します。Rust hashbrownや多くのSwiss-table移植は、伸びる前に0.875付近へ座ります。
古典的な分離連鎖の教材は0.5または1.0を狙うことが多いです。いずれの場合も計画の恒等式は同じで、n個の鍵を目標α以下に置くなら、少なくともceil(n / α)個の枠が要ります。その生の天井が、実際に確保する数になることはほとんどありません。
マスク実装は添字を一つのビット単位ANDにするためmを2の冪に求め、だから0.75における1 000個の鍵は1 334ではなく2 048個のバケットになります。剰余実装は弱いハッシュでも剰余類へ散らすため素数を好み、だから同じ1 000個の鍵は1 334以上の次の素数になります。本計算機はその二段の判断を明示します。
次の2の冪まで大きく切り上げた表は実効負荷に余裕がありheadroomも広いです。近い素数に着地した表は窮屈で再確保に近いです。計算機科学らしいという理由で1 024や4 096を当てるのは、サービスがRAMの一頁を無駄にするか、最初の一分の通信量で再確保に当たる道です。
この計算が役立つ場面と上限
HashMapの初期容量を選ぶとき、配列が1 334ではなく2 048である理由を弁護しなければならない注釈を書くとき、マスク表と剰余表の違いを査読で辿るときは、ブラウザの道具をお使いください。次の伸びの峰をheadroomが覆うまで負荷率を掃引し、丸めたmを残してください。mが分かったら衝突の期待値計算機と対比してください。
そちらは何個の鍵がバケットを共有するかを答え、本頁はまず何個のバケットを確保するかを答えます。二つの検索は別件であり、食い合ってはなりません。検証の失敗は残高を消費しません。
教室の八鍵の例から、十億件のプロセス全体のインターン表までです。結果は完全に決定的で、同じitems、負荷率、丸めは常に同じベクトルを返すので、試験と教材に例を固定できます。言語モデルも外部の統計サービスも乱数もありません。
ハッシュ表の教程、静的な表を出すコンパイラ後段、最初の挿入の前に容量を選ばねばならないサービス雛形へ、この端点をつないでください。
活用例
HashMapと辞書の初期容量
作業集合の見込み大きさと0.75(または実行系の既定)を渡し、Java、Rust、および大半のマスク型対応表が確保すべき2の冪の配列を得ます。
素数大きさの剰余表
hash modulo mで添字を付ける古典的な分離連鎖やHashtable風の対応表を、占有の床を次の素数へ丸めて寸法決めします。
生成器、査読、CIの神託
コード生成器と面接基盤は、欠けた要素数を拒み、同じnとαに同じbuckets欄を返す決定的な寸法決めの神託を呼び出します。
よくある質問
バケット数は2の冪と素数のどちらへ丸めるべきですか?
古典的なJava Hashtableのような剰余型にはprimeを使い、弱いハッシュでも剰余類へ散らします。
負荷率はどれを選べばよいですか?
使う表によって異なります。JavaのHashMapは初期設定で0.75、Rustのhashbrownなどの多くは0.875前後、教材のコードでは0.5や1.0がよく使われます。データを入れる表に合わせて選んでください。
容量と余裕とは何ですか?
容量は、切り上げた表が目標の負荷率を超えずに入れられるキーの数で、余裕は容量からキーの数を引いたものです。1000個のキーを0.75で2048個のバケットに入れると、容量は1536、余裕は536です。
どんな値を入力できますか?
キーは1個から10億個まで、負荷率は0.05から1までです。0.05未満は、使える表ではなくほとんど空の配列を表すことになるため受け付けません。
実際の負荷率が目標より低くなるのはなぜですか?
バケット数を、表が実際に確保する大きさまで切り上げるためです。1334から2048への切り上げで実際の負荷率は0.48828125になり、0.75を大きく下回るので、次のリサイズまで余裕ができます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/dev/hash-table-capacity \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"items":1000,"load_factor":0.75}'const res = await fetch("https://api.kit.forhosting.com/dev/hash-table-capacity", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"items": 1000,
"load_factor": 0.75
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/hash-table-capacity",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"items": 1000,
"load_factor": 0.75
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/hash-table-capacity", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"items":1000,"load_factor":0.75}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"items":1000,"load_factor":0.75}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/hash-table-capacity", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"items": 1000,
"load_factor": 0.75
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.hash_table_capacity",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_items | 1000000000 |
min_load_factor | 0.05 |
max_load_factor | 1 |
max_buckets | 34359738368 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
切りの良い当て推量ではなく負荷率がバケット数を決めるべき理由
min_buckets(占有の床)、buckets(丸めた確保)、actual_load_factor(n / m、丸め後は常に目標以下)、capacity(目標を越える前に入る鍵の数)、headroom(capacity引くn)を報告します。この五つの数字を揃えてお使いください。
入力契約、丸め方式、式、および誤り時の振る舞い
itemsは見込まれる鍵の数で、一から十億までの整数です。0.75は例かつJavaの既定、1.0は満杯の表、0.05未満はほぼ空の配列であり作業用の対応表ではないため拒みます。別名modeとstrategyを受け付けます。2の冪は32ビットの小技ではなく倍加で求めるので、二の三十一乗を超える大きさも正確な安全整数のままです。素数は奇数の候補への試し割りで求めます。mを決めたあとに何個の鍵が枠を共有するかも要る場合は、玉入れの占有道具と組み合わせてください。必須欄二つと任意欄一つを持つJSON本体をPOSTしてください。別名n、count、expected、keysを受け付けます。load_factorは目標αで、0.05から1までを含む有限数です。別名loadとalphaを受け付けます。roundingはenumでpower_of_twoまたはprime、省略時はpower_of_twoです。有限の定義域はenumに置き、フォームが選択欄を描き、APIが勝手な綴りを拒むようにします。検証のあとエンジンはmin_buckets = ceil(items / load_factor)を求め、積がなおnを下回るなら浮動小数の一段を補正し、その床以上の次の2の冪または次の素数をbucketsに置きます。JSONはitems、load_factor、roundingを繰り返し、続けてmin_buckets、buckets、actual_load_factor、capacity、headroom、is_power_of_two、is_prime、2の冪経路だけのbits欄(mの二を底とする対数)、およびformula文字列を返します。items欠落、公表範囲外の負荷率、整数でない要素数、未知の丸め値は、欄名を示すinvalid_inputで失敗し、課金されません。これは寸法決めの神託であり、衝突の期待個数ではありません。
バケット数APIが本領を発揮する場面、上限、および料金
コード生成器、面接用砂場、キャッシュ断片の計画器、継続的統合の点検が、一つの契約のもとで多くの(n, α)対に安定したJSONを要する場合はAPIをお使いください。成功した依頼は一件あたり$0.002の課金品目です。公表された範囲は、返るどの個数も通常のIEEE-754安全整数の内側に保ち、手で寸法を決めるあらゆるメモリ内対応表を覆います。
技術的な質問
n個の要素と負荷率からハッシュ表のバケット数をどう選びますか。
items(またはn)とload_factor(例は0.75)を送ってください。計算機はmin_buckets = ceil(n/α)と、次の2の冪または次の素数へ切り上げたbuckets、さらに実効負荷、capacity、headroomを返します。
min_bucketsとbucketsの違いは何ですか。
min_bucketsは占有の床ceil(items / load_factor)です。bucketsはその床を割り当て可能な大きさへ切り上げたものです。したがってactual_load_factor = items / bucketsは目標以下になります。
itemsが欠けている、または負荷率が範囲外だとどうなりますか。
依頼は欄名を示すinvalid_inputで失敗します。itemsは1から1 000 000 000までの整数、load_factorは0.05から1までの有限数でなければなりません。検証失敗は課金されません。
ハッシュ表のバケット数計算機は無料ですか。
ブラウザの道具はお使いの機器上で無料です。API呼び出しは成功一件あたり$0.002の前払いKIT残高を使い、検証失敗は課金されません。