How are hash tables implemented internally in popular languages?

How are hash tables implemented internally in popular languages?

Can someone please shed some light on how popular languages like Python, Ruby implements hash tables internally for symbol lookup? Do they use the classic “array with linked-list” method, or use a balanced tree?

The classic “array of hash buckets” you mention is used in every implementation I’ve seen.

One of the most educative versions is the hash implementation in the Tcl language, in file tcl/generic/tclHash.c. More than half of the lines in the file are comments explaining everything in detail: allocation, search, different hash table types, strategies, etc. Sidenote: the code implementating the Tcl language is reallyreadable.

Perl uses an array with linked lists to hold collisions. It has a simple heuristic to automatically double the size of the array as necessary. There’s also code to share keys between hashes to save a little memory. You can read about it in the dated but still relevant Perl Illustrated Guts under “HV”. If you’re truly adventurous you can dig into hv.c.

The hashing algorithm used to be pretty simple but its probably a lot more complicated now with Unicode. Because the algorithm was predictable there was a DoS attack whereby the attacker generated data which would cause hash collisions. For example, a huge list of keys sent to a web site as POST data. The Perl program would likely split it and dump it into a hash which then shoved it all into one bucket. The resulting hash was O(n) rather than O(1). Throw a whole lot of POST requests at a server and you might clog the CPU. As a result Perl now perturbs the hash function with a bit of random data.

You also might want to look at how Parrot implements basic hashes which is significantly less terrifying than the Perl 5 implementation.

Lua tables use an utterly ingenious implemenation which for arbitrary keys behaves like ‘array of buckets’, but if you use consecutive integers as keys, it has the same representation and space overhead as an array. In the implementation each table has a hash part and an array part.

vim macros

vim macros

Deliberate Software

Vim Refactoring Patterns

 22 Jun, 2016 · Read in about 5 min · (990 Words)

 technical skills vim refactoring

Editor macros are a secret weapon for editing text. While they are hard to learn, no other tool offers such broad speed and power for automating changes. A skilled macro wielder can make huge changes to a codebase with ease.

Here are some inspirational patterns to demonstrate major structural refactorings using Vim macros and search/replace commands.

Reorder A List Of Numbers

A change left me with a file with unordered numbers. The numbers needed to be increasing, without changing the actual order of the lines. Macros are my first choice to accomplish a repeated action.

The commands:

/; – Search for ‘;’n – Go to next ‘;’qq – Start macro in ‘q’ registerdb – Delete backwardsN – Search for previous ‘;’yb – Yank backwardsn – Search for next ‘;’P – Paste backwardsCtrl+a – Increment numbern – Go to next ‘;’n – Go to next ‘;’q – Stop Recording macro33@q – Replay 33 times the ‘q’ macro

This only took me a few seconds to type! I was able to run this across the whole file by replaying it the number of lines minus one. Because I saved it in the ‘q’ register, I was able to keep it saved for the whole session, which involved refactoring several dozen similar files. I got to re-use the saved macro at least 20 more times in that three hour session!

I don’t think this macro is very complex. I would only leave it in the register for a single session, and remake it in the future if needed. But if I wanted to save it, running “qp spits out: dbNybnP^ann.

buzzfeed.com: How Hired Hackers Got “Complete Control” Of Palantir

buzzfeed.com: How Hired Hackers Got “Complete Control” Of Palantir

Palantir Technologies has cultivated a reputation as perhaps the most formidable data analysis firm in Silicon Valley, doing secretive work for defense and intelligence agencies as well as Wall Street giants. But when Palantir hired professional hackers to test the security of its own information systems late last year, the hackers found gaping holes that left data about customers exposed.

Palantir, valued at $20 billion, prides itself on an ability to guard important secrets, both its own and those entrusted to it by clients. But after being brought in to try to infiltrate these digital defenses, the cybersecurity firm Veris Group concluded that even a low-level breach would allow hackers to gain wide-ranging and privileged access to the Palantir network, likely leading to the “compromise of critical systems and sensitive data, including customer-specific information.”

This conclusion was presented in a confidential report, reviewed by BuzzFeed News, that detailed the results of a hacking exercise run by Veris over three weeks in September and October last year. The report, submitted on October 19, has been closely guarded inside Palantir and is described publicly here for the first time. “Palantir Use Only” is plastered across each page.

It is not known whether Palantir’s systems have ever been breached by real-world intruders. But the results of the hacking exercise — known as a “red team” test — show how a company widely thought to have superlative ability to safeguard data has struggled with its own data security.

The red team intruders, finding that Palantir lacked crucial internal defenses, ultimately “had complete control of PAL’s domain,” the Veris report says, using an acronym for Palantir. The report recommended that Palantir “immediately” take specific steps to improve its data security.

“The findings from the October 2015 report are old and have long since been resolved,” Lisa Gordon, a Palantir spokesperson, said in an emailed statement. “Our systems and our customers’ information were never at risk. As part of our best practices, we conduct regular reviews and tests of our systems, like every other technology company does.”

cplusplus.com: How to make an Excel style tables

cplusplus.com: How to make an Excel style tables

Search:
Go
ForumWindows Programminghow to make an Excell style table
Not logged in
registerlog in
how to make an Excell style table

Oct 10, 2011 at 9:27pm
smileeFace (3)
Yeah, the title pretty much states it. I need to generate it dynamically too. Like the user enters the number of rows and columns.

Thanks
Oct 11, 2011 at 12:05am
Computergeek01 (5472)
Ok, where are you stuck? After you strip away all of the cool functionality it brings, Excel is just an array of objects with their rendering contexts displayed in two dimensions.
Oct 11, 2011 at 11:54pm
freddie1 (1409)
The generic term for what you are describing is a ‘grid’. In Windows we call them grid controls. Actually, in terms of the stock controls provided by Windows itself, i.e., the standard Windows controls (buttons, text boxes, combo boxes, etc.), or the ‘common controls’, there aren’t any grids in the full sense of the term. The closest thing is the List View Common control. Many folks have modified versions of that that allow editing cells.

Alternately, you could buy a grid custom control or make your own (its rather complex). On the other hand, if you are a do it yourself sort and like to re-invent the wheel, as I do, – think ‘array of text boxes’.
Oct 12, 2011 at 1:21pm
george135 (268)
Just embed Excel with COM or use one of the native Grid controls
Oct 12, 2011 at 7:34pm
Lamblion (642)
I don’t mean to hijack the thread, but how would you embed Excel? Is it complicated?
Oct 12, 2011 at 10:20pm
Computergeek01 (5472)
@ Lamblion: Just ignore that user, they always make some comment telling the user to use COM objects weither or not COM is even needed for to solve the problem and he NEVER follows up after a post to help users any further.
Oct 13, 2011 at 1:15am
Lamblion (642)
Okay, thanks for the head-up, Computergeek01.
Oct 15, 2011 at 12:59pm
andywestken (3990)
@smileeface – when you say you want to make an Excel style table, do you just want a basic table that people can edit? Or do you need the spreadsheet functionality, too.

(And you don’t mention what tools you use: I’m presuming Visual C++ Express, except at the very end)

If the former, then freddie’s suggestion — of using a List View control — is a good one. It’s relatively straight forward (if you know your way round the common controls and Windows GUI programming) to put together an editable table. The standard way is to use a single edit control (or combobox, etc) which is moved to cover the active cell.

CodeProject.com and CodeGuru.com have various articles illustrating this approach. One which looks reasonably clear is (it’s an MFC project, but should be translatable into normal, Petzold-style Windows code):

Editing Sub-Items in List Control
http://www.codeproject.com/KB/list/editing_subitems_in_listcontrol.aspx

And this is a shorter article which avoids MFC

How to edit listview subitems in Win32
http://www.codeproject.com/KB/list/ListsiEdit.aspx

There are asorted things you need to do to get everything to look right. for example, you’ve got to set the font used by the Edit control to match that of the List View control.

“Just” (?) embedding Excel into you app would only be a sensible way to go if you needed Excel’s full capabilities. If you have a full version of Visual C++ (rather than the Express version) then ATL and MFC both provide classses to help with this. Writing a COM container app from the ground up is not a trivial exercise (if COM, embedding, IDispatch, etc. are all new to you, this is probably not the way to go). The following article show what you’ve still got to do after you’re written your COM container application (it uses MFC)

How to embed and automate an Excel worksheet by using MFC and Visual C++ 2005 or Visual C++ .NET
http://support.microsoft.com/kb/311546

However, someone has written an old-school (using WIN32 directly) grid control: BABYGRID.

Win32 Grid Control with Low Overhead (BABYGRID)
http://www.codeguru.com/Cpp/controls/controls/gridcontrol/article.php/c5277

BABYGRID does get mixed reviews, but I’ve used it for small apps successfully. It’s prob. not the way to go if you need to handle loads of data (some people complain about its performancne).

Finally, if you do have a full version of Visual Studio, with MFC, then the following articles might be of interest.

The Ultimate Grid Home Page
http://www.codeproject.com/KB/MFC/UltimateGrid.aspx

MFC Grid control 2.27
http://www.codeproject.com/KB/miscctrl/gridctrl.aspx

Regards,

Andy

PS If you use another GUI framework — like Qt, wxWidgets, FLTK, … — then other possibilities open up.
Last edited on Oct 15, 2011 at 2:26pm
Oct 15, 2011 at 1:15pm
andywestken (3990)
PPS I was assuming you were talking about non-.Net Windows programming. If you’re using C++/CLI, then you could use DataGrid or DataGridView (Search MSDN for info).

Last edited on Oct 15, 2011 at 1:19pm
Topic archived. No new replies allowed.
C++
Information
Tutorials
Reference
Articles
Forum
Forum
Beginners
Windows Programming
UNIX/Linux Programming
General C++ Programming
Lounge
Jobs
Home page | Privacy policy
© cplusplus.com, 2000-2016 – All rights reserved – v3.1
Spotted an error? contact us

microsoft.com: How to embed and automate an Excel worksheet by using MFC and Visual C++ 2005

microsoft.com: How to embed and automate an Excel worksheet by using MFC and Visual C++ 2005

This step-by-step article describes how to embed an Excel worksheet in a View object in a single-document interface (SDI) Microsoft Foundation Classes (MFC) application by using Visual C++ 2005 or Visual C++ .NET.
Create an MFC Application that Embeds an Excel Worksheet

The following steps describe how to embed a worksheet and automate the worksheet to add data to a cell.
Start Microsoft Visual Studio .NET. On the File menu, click New, and then click Project. Under Project types click Visual C++ Projects, and then click MFC Application under Templates. Name the project Embed_Excel.

Note In Visual C++ 2005, click Visual C++ instead of Visual C++ Projects.
When the MFC Application Wizard appears, follow these steps:
Click Application Type and then select Single Document.
Click Compound Document Support and then select Container.
Click Finish to accept all other default settings.
Add interfaces from the Excel object library. To do this, follow these steps:
On the Project menu, click Add Class.
Select MFC Class From TypeLib from the list of templates and click Open. The Add Class From TypeLib Wizard appears.

Note In Visual C++ 2005, click Add instead of Open.
In the list of available type libraries, locate Microsoft Excel version Object Library. For Excel 2000, the version is 9.0, for Excel 2002, the version is 10.0, and for Microsoft Office Excel 2003, the version is 11.0.
Add the following interfaces:
_Application
_Workbook
_Worksheet
Range
Workbooks
Worksheets
Click Finish.
Add the following line to Cntritem.h as a public member function of the CEmbed_ExcelCntrItem class:
LPDISPATCH GetIDispatch();
Add the GetIDispatch method to Cntritem.cpp, as follows:

/*******************************************************************
*   This method returns the IDispatch* for the application linked to
*   this container.
********************************************************************/ 
LPDISPATCH CEmbed_ExcelCntrItem::GetIDispatch()
{
	//The this and m_lpObject pointers must be valid for this function
	//to work correctly. The m_lpObject is the IUnknown pointer to
	// this object.
	ASSERT_VALID(this);

	ASSERT(m_lpObject != NULL);

	LPUNKNOWN lpUnk = m_lpObject;

	//The embedded application must be running in order for the rest
	//of the function to work.
	Run();

	//QI for the IOleLink interface of m_lpObject.
	LPOLELINK lpOleLink = NULL;
	if (m_lpObject->QueryInterface(IID_IOleLink,
		(LPVOID FAR*)&lpOleLink) == NOERROR)
	{
		ASSERT(lpOleLink != NULL);
		lpUnk = NULL;

		//Retrieve the IUnknown interface to the linked application.
		if (lpOleLink->GetBoundSource(&lpUnk) != NOERROR)
		{
			TRACE0("Warning: Link is not connected!\n");
			lpOleLink->Release();
			return NULL;
		}
		ASSERT(lpUnk != NULL);
	}

	//QI for the IDispatch interface of the linked application.
	LPDISPATCH lpDispatch = NULL;
	if (lpUnk->QueryInterface(IID_IDispatch, (LPVOID FAR*)&lpDispatch)
		!=NOERROR)
	{
		TRACE0("Warning: does not support IDispatch!\n");
		return NULL;
	}

	//After you verify that it is valid, return the IDispatch
	//interface to the caller.
	ASSERT(lpDispatch != NULL);
	return lpDispatch;
}