Whats the fastest way to check if a string exists in a string collection in javascript?

Question

In JavaScript, I need some data structure that can hold strings, and has a fast way to search if a string exists in it, and to insert a string in it.

I was planning to use an array, but I am currently using a dictionary where the key is the string and the value is just 'true' even through I don't use it.

I went with dictionary because I would think it would be something like an AVL tree, where the insert, delete and add are all O(log(n)) time. And the array would have an insert, delete, and search of O(n) time.

Is this right, or is there a better way?

Thanks

If you use an array, you could use [indexOf](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf) — kalley, Jul 08 '13 at 18:40
kalley: isn't that still a linear search?; Barmar: see here http://stackoverflow.com/questions/5594850/is-there-a-dictionary-implementation-in-javascript; Dany Caissy: can you show me an example? — sneaky, Jul 08 '13 at 18:43
@FelixKling Anything he does with this is using it _as_ a dictionary. His question was what built-in data type he should use, and then he referred to dictionary as if it were one. — Barmar, Jul 08 '13 at 18:45
@sneaky The answer in that question uses an object. Javascript doesn't have anything we _call_ a dictionary, but its objects are like Python dictionaries, Perl hashes, PHP associative arrays, and C++ maps. — Barmar, Jul 08 '13 at 18:46
There are only two data structures, arrays and objects (whereas arrays are objects too, but you'd process them a bit differently). Which one of those is faster you can find out with http://jsperf.com/. — Felix Kling, Jul 08 '13 at 18:47

Barmar · Accepted Answer · 2013-07-08T18:55:36.363

2

Use an object.

Add string:

obj[string] = true;

Check if string exists:

obj.hasOwnProperty(string);
// or simply
obj[string]

edited Jul 08 '13 at 18:55

answered Jul 08 '13 at 18:49

Barmar

741,623
53
500
612

2

Actually, using `obj[string]` to test the existence is a lot faster: http://jsperf.com/hasownproperty-vs-in/2. I assume browsers optimize property access a lot. – Felix Kling Jul 08 '13 at 18:51
1

@FelixKling Doesn't that signal an error if the property doesn't exist? I didn't want to recommend something that signals, although I notice lots of code like that in libraries like jQuery. – Barmar Jul 08 '13 at 18:54
I think if it doesn't exist, it will be `undefined` or `null`, which you can check for. – sneaky Jul 08 '13 at 18:55
If the property doesn't exist you get `undefined` which is falsy. So `if (obj[string])` will work fine in this case. – Felix Kling Jul 08 '13 at 18:56
@FelixKling this is true and faster, but it also needs to be noted that `({})['valueOf']`, `({})['toString']`, [**etc**](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/prototype#Properties) are not _undefined_. – Paul S. Jul 08 '13 at 18:57
I know that's what it returns, but I thought it also results in an error along the way, but the error is ignored by default. – Barmar Jul 08 '13 at 18:57
Nope, no error. @PaulS: True, it depends on the use case. But if you know what kind of values you may get, then you can optimize for it :) In the worst case you can do `if (typeof obj[string] === 'boolean')` which is still a lot faster than `hasOwnProperty`. – Felix Kling Jul 08 '13 at 18:58
1

@FelixKling when I do these kinds of checks I explicity check for `true` or `1` to reduce this problem, e.g. `obj[key] = 1; if (obj[key] === 1) {/* found */}` – Paul S. Jul 08 '13 at 19:00
@PaulS.: Of course, that makes sense. Somehow I was thinking about a scenario were one has multiple different values (because that's why I made the test in the first case). But no need to make it more complicated than it is, comparing the value should be first choice here. – Felix Kling Jul 08 '13 at 19:29

score 1 · Answer 2 · edited May 23 '17 at 12:21

1

If you use an array.

You can use indexOf() to find the position. And splice() to insert a string into array object. Also if position does not matter, use push().

This should be fast enough, it is in JS library.

EDIT:

Both indexOf() and splice() are linear.

edited May 23 '17 at 12:21

Community

1
1

answered Jul 08 '13 at 18:42

Brian

4,958
8
40
56

Using this, is really faster than a dictionary? – sneaky Jul 08 '13 at 18:44
`indexOf` will still be a linear search, i.e. `O(n)`. – Felix Kling Jul 08 '13 at 18:46
JS guys would not create this if it was not :) – Brian Jul 08 '13 at 18:47
Since order doesn't seem to matter, I would just use `.push` to add a value. Certainly faster than `.splice`. What makes you think it is `O(nlogn)`? – Felix Kling Jul 08 '13 at 18:53

score 0 · Answer 3 · answered Jul 10 '13 at 14:25

var stringStore = {};

stringStore['sample-string-1'] = 'sample-string-1';

stringStore['sample-string-2'] = 'sample-string-2';

if (stringStore['sample-string-2'] ) console.log("string 2 exists"); else console.log("string 2 doesn't exists");

if (stringStore['sample-string-3'] ) console.log("string 3 exists"); else console.log("string3 doesn't exists");

Whats the fastest way to check if a string exists in a string collection in javascript?

3 Answers3