# Tag Info

10

typedef _t POSIX reserves identifiers ending in _t. You should maybe use _s also for the typedef: struct Foobar { void *foo; int32_t bar; }; typedef struct Foobar foobar_s; Or not use typedef at all. #define _MAX POSIX reserves identifiers ending in _MAX or _MIN. For your macros (or consts, but don't use enum for that) that design maximums ...

8

General Good work for a C newcomer! Welcome to the club! Thank you for providing a good test program, and for the macro to exercise the list code - that really helps give confidence in the implementation. The tests do have some limitations, since they only test inserting elements and freeing the entire table; there's no tests of lookup, updating values ...

7

Code readability and style Your code has nothing wrong with style (as far as I know). It seems to be (99.9999...%) PEP 8 compliant. I ran a PEP 8 checker over your code and this is what it picked up - Which basically tells you to add a space before the operator '=' here - hash_route= {} # hash_route = {} As for the missing newline at the end of the ...

6

The very idea of "if that hash is already taken, use another one" leads to bugs that are really hard to find later. It's because your hash function (oh, it is called a function, hopefully in the mathematical sense) no longer has the signature hash(studentNumber) but instead becomes hash(studentNumber, allPreviousStudentNumbers). This means you get different ...

5

You seem to make use often return 1. It would be better to use booleans to show a clear intention of what you want to return. Also, your hash_route, which you build as a dict, has a constant value that is never used, making it effectively a set, which is fine if all you care is the lowest common ancestor. I would go for: def traverse_DFS(root, ...

5

I think instead of adding integers to the Hashset, what we should do is insert a LinkedListNode instance into the Hashset and then to detect a loop we check whether the current node exists in the Hashset or not, if it does then there's a loop HashSet<LinkedListNode> set = new HashSet<LinkedListNode>(); LinkedListNode current = head; ...

4

If this is a class assignment, you might ask your professor why you spend time reading test data from keyboard instead of writing unit tests. Or if you really have to, at least use a Scanner to learn how the standard libraries work. That's what everyone else does in their classes. Nobody reads input from keyboard outside of the classroom in the extent the ...

4

Tests Instead of that main, which I assume you wrote for testing... You can create actual tests, with the unittests module. import unittest class HashTableTest(unittest.TestCase): def setUp(self): self.hashtable = HashTable() self.hashtable.put(1, 2) self.hashtable.put(9, 3) self.hashtable.put(17, 5) def test_get(...

3

"magic" method If you're learning the data structures in Python, I would read about the python data model and Collections abstract base classes to see what magic methods you can/should implement. A Hashmap is a mapping, so it should implement __getitem__, __iter__, __len__, __contains__, keys, items, values, get, __eq__, and __ne__ return vs exception In ...

3

It's been a long time since I've coded in C, so bear with me. #define Your implementation's #define statements puzzle me. #define is a directive, essentially a macro, best used to define constants. With that said: You should use typedef for type definitions. #define will only be respected by a preprocessor as a copy/paste directive, and nothing more. ...

3

Combining lookup and insertion functionality in one function looks like an unnecessary violation of SRP. I strongly recommend to separate them. Keeping the error inside the structure is indeed questionable. Notice that once you split lookup and insert, return errcode; becomes natural: every function besides insert would just return an error code, and insert ...

3

Here's one suggestion related to usability. Say I want to make this code work: h = HashTable() h.put('hello', 'world') h.put((1,2), (3, 4)) h.put(95.7, 76.2) I have to define a custom hash function to handle the tuples and floats as keys. The only way I can add a custom hash function, however, is to modify your hash table code and add it to the map in the ...

3

So I'm looking for the go-to solution for situation like this, if one exists Big step, small step. Rather than run the snake once, you run it twice in parallel, but the two instances run at different speeds: snake1 = ...; snake2 = snake1.clone(); while (true) { snake1.step(); snake2.step(); snake2.step(); if (snake1.equals(snake2)) { ...

3

Rreplace the inner for loop of rehashing with a call to put. put has an average runtime of $\mathcal{O}(1)$ . So, rehashing has an average runtime of $\mathcal{O}(n)$ since it is $n$ put operations. It would look something like this: void rehashing() { int oldCap = cap; sze = 0; cap = NextPrime(cap * 2); HashNode** oldArr = arr; arr = new ...

3

Struct with a single pointer Instead of making your set a struct with a single pointer (presumably to hide the implementation details of your set state), just use a forward struct declaration and force the users to only use a pointer to your set: struct unordered_set; typedef struct unordered_set unordered_set; Now your set can just be what you now call ...

3

Performance improvement A key attribute concerning hashing, capacity and doubling the table size *= 2: primes The hash table index calculation has 2 stages: hash_func() and % capacity. A poor or modest hash_func() is improved when modded by a prime. A prime will not harm a good hash function. Modding by a power-of-2 is the worst as it simply becomes a ...

3

This is a noble goal -- you will learn (and perhaps already have learned) a lot about higher level languages by diving a layer deeper. Here are my thoughts as I read your code. I hope you don't mind my stream of consciousness format. Project Layout Did you put the declarations in headers? It's definitely a good idea. I don't see any includes, so I'm a ...

3

... used Robin Hood hashing. It seems way too simple so I'm not sure if it is implemented correctly! No comment. Is it better to have an array of entries (buckets) or an array of pointers to entries (initialized with NULL)? 6.01 or half-dozen of the other. Depends on use case. I prefer a dynamic array of entries for less (perceived) fragmentation. ...

3

Bug JavaScript strings are Unicode. Your code assumes that the characters in the string are less than 256. If a character is over 256 the resulting binary encoded string will be the wrong length and the hash will fail. Typed arrays and DataView There is no need to convert the numbers to a string of zeros and ones. The conversion is a massive CPU overhead, ...

2

public Dictionary<string, List<string>> ConsecutiveMatches { get; set; } = new Dictionary<string, List<string>>(); I wouldn't allow public access to the result in this way, because I wouldn't want clients to be able to manipulate the result of the search directly. Instead I would make this result data be private and then expose it ...

2

The data structure you want is called a trie. It's often used with letters in the nodes, for doing word search (finding anagrams and so on); in your case the keys would be words and the values would be sub-tries and arrays of line numbers or other metadata. Given this input: cat dog pig dog pig cow You'd make a structure like: { cat: { dog: { ...

2

Problems with generics Entry<T>.next should have type Entry<T>. CustomHashset<T>.buckets has type Entry<T>[] but is initialized to an Entry[]. Initializing a generic array properly is annoying, but this StackOverflow question explores a few solutions. At the end of the day, there's only so much you can do about it; you can at least ...

2

Improving names: Your class has 2 size variables, which looks kinda strange. Better to rename this private static one to something like INITIAL_CAPACITY (or DEFAULT_INITIAL_CAPACITY, if you have plans adding constructor with initialCapacity parameter), because size = how many elements are stored, but this variable denotes initial array length. method hash ...

2

In your constructor, you can construct _table with just _table(capacity). In _expand_and_rehash, you're making copies of vectors you don't need to make. First, you can move table to temporary using table_t temporary = std::move(table);. When copying the data to the new table, you're creating copies of the lists. Use a rerefences in those loop: for (...

2

Use a perfect hash function What you want is to implement a perfect hash function. This is any function that for any of the valid input values, results in a unique value into to the hash table. Despite the name, there is more than one way to make such a function. Also, it's easier to make if you allow the hash table to be bigger than the number of valid ...

2

The comment // It will be very bad idea to touch e->key or e->hash here. Treat "key" as being read-only. // Caller should not hold the pointer to the entry over hashtable_add/remove/dispose calls. suggests that hashtable_get should return the value, rather than the entry pointer. The caller already knows the key, there is no point ...

2

The main piece of advice I feel I can offer is to avoid using the asterix from list2BST import * This makes it much harder for other users to work out where individual functions are coming from. It is much better practice to say import list2BST and then list2BST.<function name> or from list2BST import <function_1>, <function_2> I ...

2

Why have nested unordered_maps. Just use a single unordreed map using a key that is the x and y coordinates? One enhancement I would add is using the operator[][] to access the elements. #include <unordered_map> #include <utility> #include <iostream> #include <functional> template <typename T> class UMapMatrix { public: ...

1

Use int main(void) C17::6.11.6: Function declarators The use of function declarators with empty parentheses (not prototype-format parameter type declarators) is an obsolescent feature.

1

In my opinion this statement is quite complicated to read, compared to what you want achieve: int nextSize = currentSize % 2 == 0 ? currentSize / 2 : (currentSize + 1) / 2; You could consider using some brackets: int nextSize = (currentSize % 2 == 0) ? (currentSize / 2) : ((currentSize + 1) / 2); Or just use Math.ceil(): int nextSize = (int) Math.ceil(...

Only top voted, non community-wiki answers of a minimum length are eligible