What is Array ?
Arrays allow for quick access to elements using their index, making them highly efficient for various applications. However, as the size of the array grows, the time complexity for certain operations, such as searching for a specific element, can increase.
Array usage
Let's say we are building our own web service, and we have some validation in our response to flag all success responses. This validation can also be utilized to send out metrics or perform access logging.
interface HTTPResponse { code: number; message: string;}const successResponses: HTTPResponse[] = [ { code: 200, message: "success" }, { code: 201, message: "created" }, { code: 202, message: "accepted" }, { code: 204, message: "no content" }]const loggerMiddleware = async (request: Request, response: Response, next: NextFunc) => { const isSuccess: boolean = !!successResponses.find((sr) => sr.code === response.statusCode); if (isSuccess) { console.log('Hello there! You received a success code.'); // another operation ... } next();}
Let me explain the snippet above:
We have a constant variable called successResponses and a function called loggerMiddleware.
successResponses is a collection of success response codes and their corresponding messages.
loggerMiddleware is a middleware function that performs logging operations (in this example, it simply logs a message). The function receives three parameters: request, response, and next. Let's focus more on the response part, which consists of a field named statusCode that holds the HTTP code.
Inside the loggerMiddleware function, we validate the response.statusCode using the successResponses constant. If the status code matches any code in successResponses, isSuccess will be true; otherwise, it will be false.
It's pretty straightforward, right?
Another note is that loggerMiddleware will run every time user visits a page on our website.
Okay, everything seems to be working fine so far, we able to check all success codes and user able to visit pages of our website, everyone happy.
... ...
But we make it better!
Using Hashmap
Let's get to the point: the code above is definitely fast, especially with a small array. However, from a time-complexity perspective, it results in O(n), because we iterate through the array to find the matching element.
Can we make it better? Yes, we can make it O(1). This technique is called hash mapping. By converting the array to a hashmap and using the unique property as a key lookup, we can achieve this.
const successResponses: { [key: number]: HTTPResponse } = { 200: { code: 200, message: "success" }, 201: { code: 201, message: "created" }, 202: { code: 202, message: "accepted" }, 204: { code: 204, message: "no content" }};const loggerMiddleware = async (request: Request, response: Response, next: NextFunc) => { const isSuccess = successResponses[response.statusCode]; // it will give us either HTTPResponse or undefined if (isSuccess) { console.log('Hello there! You received a success code.'); // another operation ... } next();}
The code above will produce an O(1) solution, and this hashmap method can be used in many use cases, especially in large applications where intensive data look-ups are necessary.
Summary
We explored how to optimize frequent array lookups by utilizing hashmaps. We started with an array-based approach to check for success responses in an HTTP service, which operates at O(n) time complexity. By converting this array to a hashmap, we improved our lookup time to O(1), significantly enhancing performance, especially for larger datasets. This technique is particularly beneficial for applications requiring intensive data look-ups, offering a straightforward and efficient solution.
Why do programmers prefer dark mode?
Because light attracts bugs!