Using values as keys in arrays to reduce complexity when searching for items

Question

Here is sometime I do a lot in PHP. Searching for a needle in a haystack.

$names = [
    'Mike',
    'John',
    'Dave',
    'Tony'
];

$gotDave = in_array('Dave', $names);

The runtime of in_array is O(n) where n is the number of elements.

I often setup my lookup data structure to look like this.

$names = [
    'Mike' => true,
    'John' => true,
    'Dave' => true,
    'Tony' => true
];

$gotDave = isset($names['Dave']);

The runtime is O(1) because in php the associative array is a hashmap.

Some questions:

should I do this? is this good practice?
is there a better value for the right hand ride

Just out of curiosity: what do you mean by "*The runtime of in_array is `O(n)`*"? What does `O` stand for? — D4V1D, Jun 15 '15 at 13:15
@D4V1D It called big oh notation. You can google it for more info. — Yada, Jun 15 '15 at 13:17
If you consider the complexity then **O(1)** is better then **O(n)**. — Sougata Bose, Jun 15 '15 at 13:20
1) It's fine. 2) It's fine. 3) Consider `array_fill_keys` for more concise syntax. — deceze, Jun 15 '15 at 13:21
Note that this is not really one-to-one since you couldn't make the second array from `['Mike', 'Mike']` — Explosion Pills, Jun 15 '15 at 13:24
@Explosion I'd assume the values are unique to begin with... — deceze, Jun 15 '15 at 13:25
[_Obvious Big-O: array_fill_keys()_](http://stackoverflow.com/questions/2473989/list-of-big-o-for-php-functions) @deceze — Narendrasingh Sisodia, Jun 15 '15 at 13:33
@Uchiha Meaning what? Yes, it's a little slower than writing a literal, but I'd assume the array initialisation only happens very rarely compared to the key lookup. — deceze, Jun 15 '15 at 13:35
@deceze it's probably a safe assumption, but I'm pointing it out in case it's not. — Explosion Pills, Jun 15 '15 at 13:42

Daniel Von Fange · Answer 1 · 2015-06-15T13:41:02.713

1

Yes, that's a great solution. In fact, that is how Sets are implemented in the core libraries of most programming languages - Off the top of my head, Python, Ruby, and Java do them this way. The Go language doesn't provide a Set, and just tells you to do what you've done.

I can't think of any reason to use any value other than true ```true``. It just makes sense.

edited Jun 15 '15 at 13:41

answered Jun 15 '15 at 13:35

Daniel Von Fange

857
9
10

score -1 · Answer 2 · answered Jul 22 '15 at 11:59

-1

you can use array_key_exists() to check for the key of the array, unlike in_array which checks for values

you will have to use array_key_exists() instead of isset() in your case

answered Jul 22 '15 at 11:59

Ehab Eldeeb

722
4
12

Using values as keys in arrays to reduce complexity when searching for items

2 Answers2