はい、JavaScript で通常のオブジェクトを連想配列として使用できることは知っていますが、Java の Map の実装 (HashMap、LinkedHashMap など) に近いものを使用したいと考えています。あらゆる種類のデータをキーとして使用できるもの。JavaScript の実装に適切なハッシュ (コード/テーブル) はありますか?
Pablo Cabrera
質問する
9622 次
4 に答える
23
JavaScript では、オブジェクトは文字通りハッシュ実装です。Java HashMap は少し偽物になるので、自分のニーズを再考するように挑戦します。
率直な答えはノーです。javascript で JavaのHashMap の優れた実装があるとは思いません。もしあれば、それはあなたが使いたくないかもしれないライブラリの一部であることにバインドされており、小さなハッシュテーブルを持つためだけにライブラリを含める必要はありません。
それでは、問題を調べるために、先に進んで書きましょう。お好みでお使いいただけます。コンストラクターを書くことから始めて、Object である Array に便乗しますが、この例が退屈になりすぎないようにする便利なメソッドがいくつかあります。
function HashMap () {
var obj = [];
return obj;
}
var myHashMap = HashMap();
Java の世界からいくつかのメソッドを直接追加しますが、進むにつれて JavaScript に変換します...
function HashMap() {
var obj = [];
obj.size = function () {
return this.length;
};
obj.isEmpty = function () {
return this.length === 0;
};
obj.containsKey = function (key) {
for (var i = 0; i < this.length; i++) {
if (this[i].key === key) {
return i;
}
}
return -1;
};
obj.get = function (key) {
var index = this.containsKey(key);
if (index > -1) {
return this[index].value;
}
};
obj.put = function (key, value) {
if (this.containsKey(key) !== -1) {
return this.get(key);
}
this.push({'key': key, 'value': value});
};
obj.clear = function () {
this = null; // Just kidding...
};
return obj;
}
引き続き構築することはできますが、それは間違ったアプローチだと思います。結局のところ、HashMap 型を持っていないだけなので、バックグラウンドで JavaScript が提供するものを使用することになります。ふりをする過程で、あらゆる種類の余分な作業に役立ちます。
JavaScript がこれほど興味深く多様な言語である理由の 1 つは、この種のレスリングを簡単に処理できることにあるというのは、少し皮肉なことです。私たちは文字通り好きなことを何でもすることができます。ここでの簡単な例は、言語の欺瞞的な力を示していなければ何もしません. しかし、その力を考えると、それを使用しないのが最善のようです.
私はJavaScriptがより軽くなりたいと思っているだけです。個人的には、適切な Java HashMap を実装する前に、問題を再検討することをお勧めします。 Javascript は 1 つを望んでも余裕もありません。
ネイティブの代替手段を覚えておいてください:
var map = [{}, 'string', 4, {}];
..比較すると、非常に高速で簡単です。
一方で、ここに厳密な答えがあるとは思いません。この実装は、実際には完全に受け入れられるソリューションである可能性があります。使えると感じたら、試してみてください。しかし、合理的に単純で自然な手段を自由に使えると感じた場合、私は決してそれを使用しません.
補足: 効率はスタイルに関係していますか? パフォーマンスの低下に注意してください.. HashMap.put() で私たちの顔を見つめている大きな O があります...最適とは言えないパフォーマンスは、おそらくここでショーストッパーではなく、おそらく実行する必要があります。最新のブラウザーでパフォーマンスが低下していることに気付く前に、非常に野心的なものや大規模なデータセットを持っている. 興味深いのは、粒子に逆らって作業しているときは、あたかも自然のエントロピーが働いているかのように、操作の効率が低下する傾向があるということです。Javascript は高水準言語であり、Java の HashMap がはるかに自然で高性能な選択肢となるのと同様に、その慣例に沿った場合に効率的なソリューションを提供するはずです。
于 2008-10-22T11:39:26.007 に答える
7
ここにリストされているものよりもさらに進んだ、スタンドアロンの JavaScript ハッシュ テーブルの実装をリリースしました。
于 2009-05-15T13:37:02.733 に答える
1
「任意の種類のオブジェクト」をキーとして使用する Java コレクションは正しくないことに注意してください。はい、任意のオブジェクトを使用できますが、そのオブジェクトに適切な hashcode() および equals() の実装がない限り、うまく機能しません。基本 Object クラスには、これらのデフォルトの実装がありますが、カスタム クラスを (効果的に) ハッシュテーブル キーとして機能させるには、それらをオーバーライドする必要があります。Javascriptには同等のものはありません（私が知っていることです）。
任意のオブジェクトをキーとして (効果的に) 使用できる JavaScript でハッシュテーブルを作成するには、少なくともハッシュテーブルのパフォーマンスの向上を維持したい場合は、使用するオブジェクトに同様のものを強制する必要があります。String を返す「hashcode()」メソッドを強制できる場合は、内部でオブジェクトを実際のハッシュテーブルとして使用できます。
それ以外の場合は、投稿された他のソリューションのようなものを作成する必要がありますが、現時点ではハッシュテーブルのようには機能しません。どちらもリストを O(n) 回検索してキーを見つけようとしますが、これはハッシュテーブルの目的をほとんど無効にします (ハッシュテーブルは通常、get/put に対して一定の時間です)。
于 2008-10-22T14:16:47.903 に答える
0
ここに私がまとめた素朴な実装があります - ケパロがコメントで述べたように、大きな問題の1つは等価チェックです:
var ObjectMap = function()
{
this._keys = [];
this._values = [];
};
ObjectMap.prototype.clear = function()
{
this._keys = [];
this._values = [];
};
ObjectMap.prototype.get = function(key)
{
var index = this._indexOf(key, this._keys);
if (index != -1)
{
return this._values[index];
}
return undefined;
};
ObjectMap.prototype.hasKey = function(key)
{
return (this._indexOf(key, this._keys) != -1);
};
ObjectMap.prototype.hasValue = function(value)
{
return (this._indexOf(value, this._values) != -1);
};
ObjectMap.prototype.put = function(key, value)
{
var index = this._indexOf(key, this._keys);
if (index == -1)
{
index = this._keys.length;
}
this._keys[index] = key;
this._values[index] = value;
};
ObjectMap.prototype.remove = function(key)
{
var index = this._indexOf(key, this._keys);
if (index != -1)
{
this._keys.splice(index, 1);
this._values.splice(index, 1);
}
};
ObjectMap.prototype.size = function()
{
return this._keys.length;
};
ObjectMap.prototype._indexOf = function(item, list)
{
for (var i = 0, l = list.length; i < l; i++)
{
if (this._equals(list[i], item))
{
return i;
}
}
return -1;
};
ObjectMap.prototype._equals = function(a, b)
{
if (a === b)
{
return true;
}
// Custom objects can implement an equals method
if (typeof a.equals == "function" &&
typeof b.equals == "function")
{
return a.equals(b);
}
// Arrays are equal if they're the same length and their contents are equal
if (a instanceof Array && b instanceof Array)
{
if (a.length != b.length)
{
return false;
}
for (var i = 0, l = a.length; i < l; i++)
{
if (!this._equals(a[i], b[i]))
{
return false;
}
}
return true;
}
// Checking object properties - objects are equal if they have all the same
// properties and they're all equal.
var seenProperties = {};
for (var prop in a)
{
if (a.hasOwnProperty(prop))
{
if (!b.hasOwnProperty(prop))
{
return false;
}
if (!this._equals(a[prop], b[prop]))
{
return false;
}
seenProperties[prop] = true;
}
}
for (var prop in b)
{
if (!(prop in seenProperties) && b.hasOwnProperty(prop))
{
if (!a.hasOwnProperty(prop))
{
return false;
}
if (!this._equals(b[prop], a[prop]))
{
return false;
}
}
}
return true;
};
使用例:
>>> var map = new ObjectMap();
>>> var o = {a: 1, b: [1,2], c: true};
>>> map.put(o, "buns");
>>> map.get(o)
"buns"
>>> map.get({a: 1, b: [1,2], c: true});
"buns"
>>> map.get({a: 1, b: [1,2], c: true, d:"hi"});
>>> var a = [1,2,3];
>>> map.put(a, "cheese");
>>> map.get(a);
"cheese"
>>> map.get([1,2,3]);
"cheese"
>>> map.get([1,2,3,4]);
>>> var d = new Date();
>>> map.put(d, "toast");
>>> map.get(d);
"toast"
>>> map.get(new Date(d.valueOf()));
"toast"
これは決して完全な実装ではなく、そのようなオブジェクトを実装する方法への単なるポインタです。たとえば、私が与えたものを見ると、現在これが機能しているため、オブジェクト プロパティ チェックの前にコンストラクタ プロパティ チェックを追加する必要もあります。
>>> function TestObject(a) { this.a = a; };
>>> var t = new TestObject("sandwich");
>>> map.put(t, "butter");
>>> map.get({a: "sandwich"})
"butter"
于 2008-10-22T12:46:20.630 に答える