There’s nothing that particularly forces a language to have arrays and hashes as fundamental datatypes. Indeed, many don’t (especially older languages). However, there are a few fundamental concepts involved which indicate that these sorts of mappings make for good data structures.

Firstly, the ordered collection where you perform lookups by index number. These are a very common structure that is very useful for the case where you’ve got a bunch of things and you want to be able to walk through them one by one or look the up by some index. The key reason why this is so popular is that the variation where the collection is compact and mapped onto a contiguous region of memory — the array — is very efficient and fast with modern hardware. It is this efficiency which is why arrays are very common (though not universal). The major alternative to the array is the linked list, which are also quite common; linked lists have linear time lookup (whereas arrays have constant-time lookup) but super-cheap insertion and deletion from the middle of the sequence.

The second major category of collection is a mapping from values of one type (that supports an equality test) to another type. This is a way of realizing a whole class of very simple functions in a memory-based data structure, and it is superb for implementing all sorts of other basic datatypes. The name of these things does vary though (e.g., “dictionary”, “associative array”) as does the implementation strategy; the most common three implementation strategies are the record/struct, the mapping tree, and the hash table. Structs are very common (and are in fact a partial hybrid between dictionaries and arrays, where the key is mapped to an offset into an array/memory block). Trees used to be very common, but have become less so as it turns out they tend to have surprisingly poor performance (their memory access pattern turns out to work poorly with the way CPU memory cache predictors work, which is unfortunate). Hash tables, which were relatively uncommon a few decades ago, work pretty well: they’ve got reasonable memory access patterns and are easy to implement well (which is definitely not true of trees!). Their major down-side is that they don’t guarantee the order of iteration (though that is fixable with some extra complexity in the data structure design).

So, the real thing that languages are providing is ℤ⁺→α and α⁼→β maps. These are both generally very useful! One is done with arrays normally, because they are easy to implement and highly efficient for lookup (typically the most common operation), and the other is done with hash tables (or structures) normally, again because they are easy to implement and usually efficient for lookup. The reason why these two particular maps? They turn out to be sufficient for creating a great many other structures with minimal extra code (which in turn means minimal extra mistakes).

Is there anything special about those datatypes that is necessary for the completeness of the language?

Nope.

Many languages don’t have hashes as a fundamental data structure in the language. And indeed, there are examples of languages that don’t have arrays or lists either. (BCPL for instance).

And many languages have other fundamental data structures; e.g. structs, unions, classes and so on.

The real answer is that there is a complicated trade-off between expressiveness, simplicity and implementability that the language designer has to make. Depending on the nature and purpose of the language, different choices are more appropriate. One of the choices is whether a particular “useful” data structure requires linguistic support, or whether it is better provided as a (standard) library.

_{My comment received a lot of up votes, so I am expanding it as an answer.}

This question’s premise takes a narrow view of what programming languages actually have. Plenty of languages in the ML family have lists rather than arrays (head/tail semantics instead of random access). And C doesn’t have built-in hashes at all. Also, q/kdb+ has a table container that mimics an in-memory SQL-like database.

Having said that, all practical programming languages have loops and/or recursion. This kind of control flow requires that data can be addressed indirectly.

For example, I can’t give a unique name to all of my data. That is, I can’t call my variables alpha, bravo, charlie, etc.; not only will I run out of names, I’ll also be unable to generically reference one variable in relation to another.

So instead I must have indirect addressing, like x₁, x₂, x₃, etc. This is very nature of arrays! Alternatively, I can take a recursive view and investigate first-of-xs and remainder-of-xs. As long as I have indirect addressing, I can use loops or recursion.

As @DonalFellows mentions in the comments, there are models of computation that are Turing complete and yet don’t have indirect addressing. Nobody actually writes code that way though.

So from a practical standpoint, I believe that arrays or lists are required for completeness in a programming language since they support the traditional control-flow mechanisms. All other containers like hashes and tables are more for convenience.

You’ve got two basic choices. You have either direct memory access (malloc with C and the resulting pointer arithmetic) or you have to provide some basic data structures to the programmer.

The first, and simplest data structure is a list of some sort (be it implemented with an array or a linked list or some other list structure behind the scenes).

With a list, one could ask the programmer to write his or her own map / associative array / hashtable / dictonary structure. Most people who have taken an undergraduate data structures class have done this. The problem is, most people have done it poorly.

To both make good use of the computer (by not having another poorly implemented hash function) and the programmer’s time (to not have to write another poorly implemented hash function again and again – think back to C, basic, and fortran days), many language designers have incorporated this structure into the base language – either as a base structure (perl’s %hash) or as part of the standard library (java.util.map).

These really end up as the only two basic structures necessary (and really, only the ability to have a list/array/block of indexable memory is critical). With them, one can build sets, trees, skip lists, and all the rest of the complex data structures that one can dream of.