## Thursday, 15 February 2018

### My Mother - In Memoriam, Part 2

My mother's short autobiography describes her early life. I can't add much to that, for the obvious reason that I wasn't there, but there are a few more details that can be tacked on.

She describes her brother and his untimely end, but what she doesn't say is how close they were. He was her very protective big brother, nurturing her at a time when her parents didn't have much time or attention to give her. His death left a huge gap in her life which in some ways was never filled.

To stretch the pennies we ate various kinds of offal when I was a child. Liver was a favourite, as was steak and kidney. But one thing we never ate was tripe - the lining of a sheep's stomach. The reason is simple - she doesn't mention that the flat in Southwark was next door to a tripe yard, a place where lorries loaded up with piles of raw tripe would arrive, their load broken down into smaller lots for distribution to the butchers' shops. I've never eaten tripe in my life. Just sitting next to people eating andouillette - French tripe sausage - once turned my stomach. The smell of lorries full of the stuff must be foul beyond belief.

My parents met at a dance, soon after the end of the war in 1945. My Dad had been married before the war, and had a daughter (Anne) in 1938. He spent the war, all of it, teaching soldiers Morse Code in North Wales, and his marriage didn't survive the separation. He was 17 years older than my mother, but very handsome for his age and very charming.

They married in 1949, living in a single room in a house in Brixton that they shared with my mother's sister and her husband, and their mother and father. (Later the house, 22 Normandy Road, was the sparking point for the Brixton riots in 1985). Anne came to stay with them, at 12 years old. It must have been very cozy. She had her own place to sleep, but when the LCC inspector came to assess them for a home of their own, she moved all their things into their bedroom. The ruse worked, and they were assigned a brand new council house on the outskirts of London, in the new development of Harold Hill. That was where I spent the first 9 years of my life, at 61 Hilldene Avenue with a busy bus-stop directly outside the bedroom windows - maybe the reason why I became fascinated by London's buses.

My father worked in a shop selling haberdashery - a quaint word now, meaning all the accessories associated with making clothes - to East London's "rag trade". He earned very little, so it was imperative for my mother to make some money if we were to live at anything beyond a subsistence level. She was an extremely accomplished typist, achieving a speed of 90 words per minute. On a modern electronic keyboard that is very fast. On a manual typewriter, where every imprinted letter is a direct result of the typist's physical strength in her fingers, it is truly extraordinary. It was astounding to watch her type, almost like watching Yuja Wang play the piano.

Before I was old enough for her to leave me with anyone, she took on typing work at home. That meant we always had a nearly-new manual typewriter, and when she wasn't working, I used it too. I never learned to touch type, but thanks to that home-work, I became a formidable two/three/four finger typist.

She started working again when I was very small, even before I went to school - needs must. We'll gloss over the dreadful woman who was supposed to take care of me - this is my mother's story, not mine. For a long time she worked for an accountant, Stuart Lever, typing balance sheets and profit and loss accounts for his customers. She had to stop that when my brother David was born, when I was 7.

Money was still very short, though. Somehow she had to earn some, even though she couldn't work during the week. Her solution was weekend work, on Saturday taking calls from punters at the bookmaker's William Hill, and on Sunday checking pools coupons at Zetters, then one of Britain's biggest football pool companies. That lasted for three or four years, during which time she was promoted to floor supervisor at Zetters. The training came in very handy for me when, later, I also worked there for pocket money while I was still at school.

As soon as my brother was old enough to be looked after, it was time for her to get full time work again. For a while she did secretarial work for the District Bank, one of the predecessors of today's NatWest. I must have been about 12 when she took the job of personal assistant to a City estate agent (realtor), Marcus King. He was a very interesting character, a doyen of City life, a central member of the Rotary Club and involved in all sorts of societies and institutions. To make it more complicated, he was also an orthodox Jew, respecting all of the dietary and other laws imposed by his religion. There are some easy and well-known ones - no pork of course, and no mixing meat and dairy. But there are dozens more, and it was my mother's job to make sure that in all of his lunch and dinner engagements, they were all respected. She probably knew more about the constraints of orthodox Judaism than any other gentile in the country. Even now I can remember words like mezuzah (a charm placed on a doorpost) and yamulka (the Jewish prayer cap).

Marcus King owned a Rolls Royce Silver Cloud, which he parked in the street outside his office in Cheapside. One day it broke down, and it fell to my mother to call Rolls and try to persuade them to come to the rescue, as they were reputed to do, before some lesser garage had to rescue it. They refused. So much for tradition.

I've mentioned only her professional life. Meanwhile, though, she was raising her two sons and her step-daughter, and generally taking care of the family. In those days it was considered normal that men didn't deal with household stuff, beyond buying the paraffin for the kitchen heaters, and so she was also responsible for cooking meals every day, and for keeping the house tidy and organised. For a good few years it was my job to take the washing to the launderette every Saturday.

As a mother she was very demanding. There was never any doubt of her love for her children, but her own upbringing had taught her not to make it too obvious. When, at 11 years old, I moved to a Grammar School, I was told in no uncertain terms that I would have to make a serious effort to compete with the smart kids from the middle class areas that the school also took in. As it turned out, they weren't very smart at all, and academically I did very well. I don't remember ever being praised for it though. It took me many, many years to overcome my resentment about this, for never being given any appreciation or praise or even encouragement. But maybe it was also an incentive to strive and try harder, and maybe such success as I have had would have eluded me without that kind of pressure.

Public displays of affection were not at all the thing of my parents' generation - just think of Brief Encounters, one of my father's favourite films. I can only recall seeing them hold hands just once. It shocked me so much that I still remember the details of the occasion - I was about 11, and we were walking along a road at North Woolwich, by the famous Free Ferry. I certainly never saw them kiss, or show any other sign of intimacy.

I can only remember seeing her cry once in my whole life. We had cats on and off throughout my childhood, and one of them got very sick. His rear legs had been paralysed by eating slug poison, which happened to be both very attractive to cats and to destroy their nervous systems. Ugh. The poor thing was dragging himself round by his front paws, and there was only one thing left to do. My mother sobbed for that poor cat.

When I think of her professional life, I think of a company called Roha, and Harry Schmiedl. She had done some temp work for him earlier, before Marcus King. Some time in my teens, he called her and told her he needed her. And that was the rest of her career. Schmiedl was quite a character, the classic East European Jew made good. He had left his native Czechoslovakia in 1937, for obvious reasons. In London he sold cloth from a barrow in street markets, gradually building up enough money through his financial savvy to start his own company, Roha. He had a big house in Hampstead, and drove a Jaguar Mk X - the ultimate arriviste motor in those days.

She worked for Roha for about 20 years, until her retirement at 60. They were "textile converters". A company, typically a big retailer - their biggest customer by far was Marks & Spencer - would decide on say a dress for their summer collection. They would decide on the fabric and the design. Roha would then find the mills to make enough fabric, the printers to print it, and all the rest of the complicated logistics involved. They made their money by taking a margin on the deal, and as you might imagine Marks & Spencer drove a hard bargain. But Schmiedl was up to the job. He carried with him a tiny Curta mechanical calculator, which he would twirl frantically while on the phone to suppliers and customers to figure out how to get his wafer-thin margin. (I wonder what happened to that calculator? They are sought after antiques now, worth \$1000 or more on eBay).

While doing deals made the money, most of the work was in the logistics of manufacture, shipping and printing. My mother excelled at this kind of organisation, and her talents were quickly used to the full. She travelled frequently, most often to the mills and printers in Germany, Alsace and in northern England. She visited Germany often enough to become a competent German speaker. Often she carried huge samples with her, like on the occasion when one of them became so firmly wedged into a corner of the baggage hold (no containers in those days) that it took over an hour to dislodge it.

From being the boss's secretary she became a Director of the company - the British equivalent of a VP. Today she would have been called the Chief Operations Officer. It was typical of her though that she refused to accept a corresponding level of pay. It was always in her mind that one day she might want to quit, and go back to secretarial work. Both of my parents were horrified at the thought of anything ostentatious, and I think that was part of it too.

A little story about that... when I was about 17, Schmiedl insisted on her having a company car. Back then this was a huge tax advantage. Rear-view mirrors then were bolted to the wings by the selling garage, not built in to the doors. They called to ask whether she wanted plane (flat) or convex mirrors on her new 1970 Ford Escort (EUC 996J - funny how I still remember that). My mother heard this as plain - as in not fancy - and was certainly not going to have anything fancy on her car.  A pity, because convex mirrors give you a wider field of view, which can be very useful.

I left home to go to university in 1971, when I was 18, and married not long after. For the next 17 years visits to my parents were en famille and while we remained firmly in touch, the daily conversations weren't there to stay in touch with events. My father retired in about 1978. Under considerable pressure from my mother, he started for the first time to take part in the general running of the house. In the same year my brother left home, too. With all three children out of the way (my sister Anne had married in 1964, although she lived only a couple of miles away), they started to travel. Holidays in Yugoslavia and elsewhere in Europe were common. Until then, my father had barely ever left Britain.

Our relationship changed again in 1988, when my own marriage broke up. For three years I lived alone on the other side of London, and would often travel over in the evening to spend an evening at the family home, and spend the night in my old bed in my old bedroom. But at first, things were very difficult. My father, especially, was very upset at this turn of events, and for several months didn't speak to me. It was my mother who brokered a truce. At first I would meet her in secret for lunch or dinner in London. Then she accepted to meet my new partner over dinner. I think she probably told my father to get over it after that, because our relationship returned to normal soon after.

Not long afterwards I had a skiing accident. It happened in France but I was fixed up at a hospital a few miles from my parents. They came to see me every day, and taught me to play Killer Scrabble. It's like ordinary Scrabble, except viciously competitive. If you leave a triple word score open, you can be absolutely sure that your opponent will find a way to use it. Later I spent a few days convalescing at their home, sitting in their garden enjoying the spring sunshine. And playing Killer Scrabble in the evenings.

Both my parents were keen gardeners. My father did all the heavy work, digging the garden over every spring for planting, cutting the grass and so on. It was mostly my mother who took care of the actual plants, and everything else once my father had passed on. She loved her garden. It produced massive amounts of fruit, especially raspberries. We moved to that house when I was 9. The previous tenants had planted raspberry canes, which in the English climate propagate like weeds. They bear huge quantities of delicious fruit over a very short time, to the point where she couldn't even give it away. There were also blackberries, gooseberries, redcurrants and apples, as well as decorative flowers.

In 1988 my mother retired. Roha had changed completely by then. Harry Schmiedl had retired and the company was sold to a Manchester-based conglomerate. She had had enough of it all, and was very happy to leave it behind. She applied her organisational talent and drive to the local retired people's activities. When I was a small child, my parents had been one of the major forces behind the Pensioners' Pals, a kind of support group for the old dears on the estate. Now that she was one of their number, she organised cross-channel shopping trips and outings all over Britain. She kept that up until she was well into her 80s. She knew all the local coach operators and could haggle the best deals for a day trip to Calais for a busload of pensioners.

In 1991 we had a big family celebration for my father's 80th birthday. A year later he was seriously ill, and he passed away in February of 1993. I moved to France at the end of 1991, but got back to England often, and visited Romford every few weeks. There would be an excellent dinner of one of my childhood favourites, steak and kidney pie for example, a bottle of wine, a chat after dinner. And then a session of Killer Scrabble. We usually found time for three games, which we won in about equal measure. Right up to my very last visit in 2014, she never lost her touch. The routine stayed much the same when, from 1997 to 2001, I spent most weeks in my flat in London, and then after I moved to the US in 2001 - though the Scrabble sessions were sometimes cut short as I fell asleep from jetlag.

Always I slept in my old bedroom, the same place where I spent every night from 9 years old to 18. There was a bookcase beside the bed, with books that my father had bought with cigarette coupons before I was born - the Readers' Digest series of DIY companions, 100 Years in Pictures with its picture of the Tay Bridge Disaster (1879) that so impressed me as a child.

She visited us a couple of times in California, enjoying every minute of it. One moment I especially remember: we were flying back from San Luis Obispo in my plane, in and out of the tops of the clouds. It's a very spectacular feeling, almost like flying into a wall except it doesn't hurt. And my mother said, "When I was a little girl, I imagined that going to heaven would be like this". On her final visit we went to Yosemite, the first time she had been there, and to Mono Lake.

My mother was an avid reader throughout her life, though she bought very few books. The local public library was her resource, an extraordinary place with a far greater wealth of books than one would ever have expected. Every week she borrowed her limit of four books, often biographies, and read them all. During my childhood we had just one small bookcase in the living room containing the couple of dozen books that we owned - my Eagle Book of Trains and Beezer annuals for example - together with our library books. Children copy their parents, and I took it for granted to visit the library a couple of times a week and to read in every spare moment, including at the dinner table. One of the saddest things, when she became ill, was that she lost all interest in reading.

Our last Scrabble evening together was in June 2014. Not long afterwards, she fell and never recovered fully from the botched operations to repair her femur. It would be too sad to talk about anything that happened after that. Now she is at peace, and no doubt already telling the angels how to run the place.

## Monday, 12 February 2018

### My Mother - In Memoriam, Part 1

A few days ago my mother passed away. She was 89, and for a while had been steadily deteriorating following the all-too-common "old lady fall". That's not how any of us want to remember her, though.

My mother was an extraordinary woman, who starting from poverty and with little education, managed to make her way successfully in the man's world of business as a fearsome organiser and manager. She was also a wife and mother, who raised three children - her own two sons as well as our father's daughter by his first marriage - with love and devotion.

Shortly before her fall, she was persuaded to write a few pages about her early life. They stop rather abruptly, most likely because she wrote them in a single session and that is where the evening ran out. But it happens to be shortly before she met my father, in 1949 or so, so it makes a natural break.

I've written my own memories of her here.

Here is what she wrote.

My history
I must have come as a terrible surprise to my mother, as she'd already had two caesarean births and, in the year 1928, to have a third child by this method was decidedly chancy! However, obviously I arrived and we both survived, even though I understand my poor old Mum was decidedly the worse for wear. The two previous children, were my brother, who was twelve years older than me and my sister, three years older than me.
From what I was told, my mother must have suffered from what is now known as a 'clicky hip', but at that time she was told it was the result of tripping up a kerb when she was about two or three years old, and, having been confined to bed for a number of years, ended up with one leg considerably shorter than the other - and was what we could now call disabled, but was then called crippled. She eventually wore a high boot to make it possible to walk although, when I was younger, I can remember her walking in normal boots but on the toes of the shorter leg. Despite this, she lived what was then a normal life. Nowadays it would be considered the heights of deprivation. I only realized what the real problem was when my first granddaughter was born with a 'clicky hip', that is a dislocated hip, and I was asked if there was any history of it in the family which, of course, I denied and it was only after further cogitation that I realized it was the true diagnosis of my mother's problem. My granddaughter was treated as a baby and lives a normal healthy life, but my poor Mum was born before it was discovered it could be treated.
I believe we were then living in a small flat in a shared house when I was born, but when I was little, we moved to the sixth floor of a tenement block in the slums of the Borough of Southwark, just south of London Bridge and the City of London. We lived on the sixth floor, because it was cheaper. My mother used to take in other peoples' washing, which had to be washed, boiled in a copper, mangled (i.e. put through a wringer) dried and ironed, and she did this just to supplement the very poor wage that my Dad brought home. She even had to carry the washing up and down all those stairs (99 of them!). Just think, no washing machine, no dryer, no vacuum cleaner not even an electric iron; no labour saving aids at all. In addition to that, there were coal fires to heat the flat. Imagine the coalman having to deliver up all those stairs!

I realise that I haven't mentioned my father, but I suppose that's because he impinged very little on my early life. Remember, it was at the time when fathers were only expected to bring home a wage and all the other family necessities were the responsibility of the mother. In fact, my Dad was born in Glemsford in Suffolk and was very much a countryman. He came to London because of the difficulty of earning a living wage in the country, but I have no idea what he then took in the way of work. Nor do I know how he and my mother met, or when they were married. However, he was in the army during the first World War, 1914-1918 and, in 1916, my brother was born. Very little was paid to the wife and family by the army and it must have been very hard-going for my Mum. My Dad was wounded while in France fighting the Germans; he was hit by a sniper, but it wasn't sufficiently bad for him to be discharged. The discharge only happened at the end of the War and, as far as I know, he then went to work for John Gardner, a wholesale caterer, as a 'handyman'. He was still working there when he retired, at the age of 70, and he died from a heart attack the following year.
My sister was born in 1925 and during childhood we were never good friends, I suppose primarily because of the three years difference in age. However, later in life, we became much closer.
During my childhood, my sister and I were regular churchgoers and it was a high church, i.e. we had what was almost a Catholic service. The church was called All-Hallows, and the vicar from there used to visit my mother regularly. Because I was such a sickly child at one time he suggested to my mother that I would benefit from a visit to a country home run by Church authorities which he could arrange, and we eagerly accepted (bear in mind that I'd never had a holiday in my life). Then it was declared that it was obligatory that I should have a smallpox vaccination before going, so this was done, but then it turned
septic, and I was treated to hot fomentations for about six weeks, and I never got to the country. This was one of the big disappointments of young life. I also recollect having diphtheria when I was four years old - I was sent to an isolation hospital, Hither Green, and did not see any of my family until I was discharged four weeks later. By the time I left, I'd become accustomed to living in a large space (hospital ward) and my mother was very disappointed when, on arriving home, I said how small everything seemed.
One joy of my early life was Sundays. Sometimes on Sunday mornings, my brother would take my sister and me for walks; usually along the banks of the Thames, which were so close to us. At the time of my childhood, there was a beach by the Tower of London, and occasionally we went there, but usually we walked along the south bank. I can still vividly recall the smell of the brewery which was there and, in fact, when I went to live near Romford later in life, the smell when they were brewing at the brewery there reminded me of my childhood. One of the other joys of Sundays was to visit my father where he worked as a Sunday watchman (no security guards then) at the headquarters of John Gardner. We used to take a full Sunday dinner plate, wrapped in towels to keep it warm, so that he didn't miss out. While we were there, we could sometimes get into the cab of a lorry, and pretend to be driving it. But the biggest joy of all was to visit the bakery, which was packed with trays full of every sort of cake imaginable, certainly not the sort of cakes we had in our everyday lives. Then there was the charcuterie, with the smell of all sorts of meats. It was an adventure for us, and whose turn it was to take my Dad's dinner was highly contested - either my brother or my sister and I together.

I passed the 11-plus exam and was entitled to go to Grammar School, but my family couldn't afford the necessary books or uniform, so it was decided I would continue at secondary school, but the Second World War intervened in Septemer 1939 just before I was due to start. I wasn't evacuated, but most of the schoolchildren went and London schools closed down for a while. Those of us who were left in London used to spend our time collecting shrapnel from the anti-aircraft guns. When the schools re-opened we only had part-time because many teachers were still with the evacuees. Also, we couldn't use the whole school, as the AFS (Auxiliary Fire Service) had the ground floor for their use, The cookery room in the grounds of the school was used as a British Restaurant, which was another war-time organization, where you could get what were purported to be healthy and cheap meals. However, when they were short staffed, we girls were recruited to do jobs like peeling potatoes — it wasn't very educational. In fact, during my last few years at school, I received very little education, because (there being no school secretary at that time), the headmaster used me to collect registers, dinner money, etc and various other jobs. This would explain why my knowledge of history, geography and other subjects which are normally learned in secondary education as almost non-existent. However, as I shall explain later, I did continue learning after leaving school by going to evening classes after I'd finished work for the day.
At that time, the school leaving age was fourteen, and there was no question of continuing unless you were at grammar school. During the run-up to my birthday, we were given various options for interviews and one of them was for office work at the head office of Odeon Theatres, a company which owned a chain of cinemas, nation-wide. I was accepted and worked as a 'post-girl', which necessitated collecting post from various departments on five different floors, and mailing it either to the cinemas or to the film rental companies, and we had pigeon holes for all of them. However, I had been attending evening school for a shorthand, typing and English course and, because some of the girl employees were being called-up for the armed services, I was promoted to secretarial work at the age of fourteen years and nine months! I was working for a booking-clerk, i.e. we had to book the films for an area in the north-east of England and, although most of these depended on what was on the Odeon circuit, it involved booking short films to make up the programme time and, because the man I worked for was a bit idle, after I'd been working for him a few months, he left this to me — I must confess my preference was for cartoons. We had a supervisor who used to sit at the front of the office and she was very strict, with behaviour which wouldn't be tolerated in this day and age. She would call out things like "Miss Slater (that was me) you have too much lip-stick on today".
We had a good crowd of girls there and we used to go out together in the evenings, even though it was during the war and there were problems with bombs, etc., and we used to have some very good evenings together despite the fact that my mother insisted I should be home by 11.00pm. One of the problems was that, if there was an air raid warning in effect at the time I was travelling home, the part of the London underground which went under the river was closed down — so I used to get off at the north side of the river and run across one of the bridges until I reached the nearest station on the south side of the river; this despite the fact that anti-aircraft guns were firing and the shrapnel was falling all around me. This worried me far less than getting home late and my Mum telling me off.
There were, of course, many incidents during the war which stick in my memory. During the time I was still at school, my mother insisted that I accompany here to the tenement where we used to live, as they had a cellar which was purported to be bomb-proof. Unfortunately, one night while we were there, a land-mine was dropped at the other end of the tenements, and all the casualties were brought down to our shelter - so, after that, I wasn't made to go there any more. One of the worst sides of the shelter was that we slept six children on a mattress sideways on, and, when the nit-nurse visited our school, she discovered that I had lice in my hair. Oh, the shame of it! You can imagine how ruthlessly my mother got over this problem.
In the street outside our house there were so-called shelters built, but the only purpose they served was that, if a bomb dropped on the house, you wouldn't be buried in the debris. Nevertheless, once again I was made to go to one of them with my mother. The children in there were allowed to lay down, but there was no room for the mothers to sleep, so my Mum used to sit on a chair all night. One night she was knitting when a bomb was dropped very nearby, and a knitting needle went through the middle of her hand. However, that was the sum total of our families' injuries during the war.
One thing I haven't mentioned is my brother's problem. He was 22 years' old when war broke out, and for about six months had been treated by our doctor for a swelling in his knee and with hindsight, I realise that the doctor had been mistreating his problem.
Early in the war he was called up for the forces, and during his medical exam, it came to light that he was suffering from tuberculosis in his knee. The treatment for it at that time was to immobilise the affected limb, so he was sent to a sanatorium in Ascot, and his leg, from the hip down to his ankle was set in plaster, and he was bedridden for four or five years. After this time, it was proven that this 'treatment' was ineffective, so he was sent to St. Thomas's hospital in London to have his leg amputated. What a pity he hadn't been born later after penicillin was discovered.
After recovering from the operation, he was fitted with an artificial leg and, being very positive, he was determined to live as normal a life as possible. After working hard at this, he got a job in the Strand, mending Ronson lighters - then found himself a girl-friend, and they got married. Good luck to him, but all the travelling and the work proved to be too much for his body to cope with and, at the age of 33, he died from a heart attack.
Reverting to my own life, and when I was working for Odeon, one of the advantages of the job was that we had a free pass for any Odeon cinema for oneself and a friend, which we could use every week, and believe me we took advantage of it. Also, when the West End cinemas were in the last week of their run, we got free tickets for them also.
The second world war ended when I was in my seventeenth year, and, of course, there was great rejoicing. But, food and clothes rationing continued for many years after that and there was a great deal of disillusionment when soldiers were demobbed and realized that life was not as easy as they had thought while dreaming of coming home. There were many disappointments.
However, now seventeen years old, after working at Odeon for just over three years, and by then being a fully qualified secretary, I decided it was time to change to another job. The Company I chose (or which chose me) was called Rootes, who used to manufacture Hillman, Humber and Sunbeam-Talbot cars and Commer and Karrier commercial vehicles. I worked as secretary to the Advertising Manager. The office was on the mezzanine floor of a building in Piccadilly called Devonshire House, and our office overlooked Green Park, so it was a very pleasant situation. There were two types of girls working there in clerical and secretarial jobs — at one end were girls with a normal education and, at the other end, there were ‘debs', who thought they were the cats' whiskers and very much looked down on us. The two types never mixed at all. When I was washing my hands in the toilet room one day, I heard two of the debs discussing the fact that normal girls were not good workers, and I challenged them to try to type or shorthand quicker than me, but they didn't take me up on it.
During that time I met a boy called John Davis and eventually we became engaged to be married. Because his parents' marriage had broken down, he lived with his grandparents in quite a grand house in Putney, and their back garden overlooked the river. We were both really too young to settle down, and I broke off the engagement because of what happened one evening. We were at a boozy party and an argument broke out between John and one of his friends, which developed into a fight. John got hold of an empty bottle and smashed the neck of it to have a go at his friend. I knew then that, when he'd had too much to drink, he was liable to become violent and I was certainly not planning a marriage like that, having seen too much of it in "the buildings" when I was younger.

## Thursday, 8 February 2018

### A Weekend in the Japanese Countryside

It's December, so it must be Japan. Every couple of years my wife has a meeting in Japan, each one threatening to be the last ever. The time has come around again, and as always we made an adventure out of it. It's getting harder to find places to go - we've long since covered all the standard tourist destinations, and have been from Ibusuke in the far south to Wakkanai and Utoro in the far north.

This time we picked Kinosaki Onsen and Amanohashidate, a couple of hours north of Kyoto on the Japan Sea coast. They're both very well known in Japan, even though none of our Japanese friends have been to either. Amanohashidate is one of the "three scenic views of Japan", designated in 1643 by Hayashi Goto (rather like the 1855 classification of Bordeaux wine). The name means "bridge to heaven", referring to the long sandspit across the estuary. But more of that later.

We flew with JAL to Haneda. After years of flying to Narita, Haneda is such a pleasure. Despite being the fifth-busiest airport in the world, it never has any queues or congestion, and it is only a short subway or monorail ride from central Tokyo. From doors open to our hotel was just 45 minutes, including immigration.

For our couple of nights in Tokyo, we stayed at the Park Hotel in Shimbashi. It starts on the 25th floor of a new skyscraper, so the views are fabulous. Ours included the Tokyo tower and Fuji, magnificent as always behind the mountains that surround the Tokyo plain.

 Train tracks from our room, with seven out of eight tracks occupied.

For me another special view is down over the eight parallel tracks of the railway leading south from Tokyo station. In the rush hour, the Yamanote and Keihin-Tohoku lines are so busy that on the mile or so of visible track looking south, there are nearly always four trains visible, one on each track. Sometimes you even get a bonus, with one train leaving the station at Hamamatsucho as another arrives. The southerly view adds another four tracks, the Haneda Monorail and the tiny trains of the Yurikamome Line. My record for the maximum number of trains visible at once stands at nine, which is probably not possible anywhere else in the world. Though it doesn't stop me hoping for better!

On the first day, my wife was in meetings. I decided to go to the Japanese National Railway Museum which is out in the suburbs at Omiya. This is a name you see on trains all the time, because it's the northern terminus of the Keihin Tohoku line. It seemed natural enough just to hope on a blue train at Shimbashi station, and stay there until it terminated. Bad mistake. Not only does it stop everywhere, but a couple of times it stopped for longer than 5 minutes. Train delays are very rare in Japan, but they do happen. On the way back I took the Utsunomiya line, which runs parallel but makes about one third the number of stops - one of which is Shimbashi, so you don't even need to change trains.

 One of the first locomotives in Japan... British of course
The museum at Omiya is really excellent, and absolutely worth visiting to anyone interested in trains. As compared to the British equivalent at York, one big difference is that it is a lot more relevant to modern trains. Many of the exhibits are electric trains very similar to the ones still running. (Embarrassingly, I have travelled on quite a few of the exhibits when they were everyday workhorses). There are also exhibits from the very early days of Japanese railways, including the first steam locomotive - built in Britain, naturally, as was the first heavy freight electric locomotive on display. It's kind of sad for Britain, though, which now imports its top-notch trains from Hitachi in Japan.

Omiya station was an interesting place. You could live your whole life without leaving it, at least without stepping outdoors. It has a department store, restaurants - and a railway enthusiast shop. It was here that I managed to find my JR system timetable. A few years ago these were ubiquitous, every station kiosk and every bookstore had them. Then along came the web, and now it's much easier to figure out your journey using an online service like HyperDia. The timetable book is near impossible to find, only anorak train spotters (like me) want it. On my previous trip I didn't manage to find one even at Tokyo station.

I spent a very pleasant evening with my Japanese friends from my Cisco days. And then it was time for the adventure to start.

Getting to Kinosaki Onsen from Tokyo is not simple. I was glad that HyperDia worked out the details for me. We took the Nozomi Shinkansen to Kyoto, and then a normal express train from there. We had 20 minutes for the connection, which seemed plenty, but we had to hike the whole breadth and length of Kyoto station's 20-odd platforms, so it was quite tight by the time we got there.

 Retro-style wood interior of the Kyoto Tango train
When we eventually found our train - the Hashidate - it was quite a surprise, very different from a typical JR train. It was short, just four coaches, and painted deep blue like the Orient Express. Inside, it had a very striking light-coloured wood finish, a cross between steampunk and a steam launch from the 1920s. Even more surprising, it was a diesel - just about every railway of any consequence in Japan is electrified. It was also very full, with nearly all the seats taken. Although most of the journey is on JR tracks, this train is operated by the private Kyoto Tango railway (named after the area it passes through, not the dance). The design makeover of the trains was done by a famous Japanese designer, and it is very successful - both inside and out, they are both striking and very attractive. The light wood finish could only work in Japan - anywhere else it would be a scruffy graffiti-covered mess, but in Japan it still looks like the day it left the workshop.

After an hour or so came the slightly scary aspect of the journey. We knew we had to change trains, with just one minute between the arrival and the departure. I figured - and certainly hoped - that this would be a cross-platform change, which indeed it was. Every hour two trains pull into Fukuchiyama station alongside each other, one coming from Osaka and the other from Kyoto. Passengers hop across the platform and then they glide out again, one to Kinosaki Onsen, our destination, and the other to Amanohashidate. It makes four trains for the price of two. Another thing that could only work in Japan - anywhere else, one of them would be late, leaving you to stand around on a cold platform for nearly an hour waiting for the next one. Which would be cancelled anyway.

 Nishimuraya Honkan garden
All three nights of our weekend were spent in traditional Japanese inns, or ryokan. Our first, the Nishimuraya Honkan, was very luxurious, a member of the prestigious Relais et Chateaux club of high-end hotels. Our room looked over a traditional Japanese garden, very mysterious and covered in moss. All these places work the same way. The room has a traditional tatami floor, with no fixed furniture. The evening meal is served in the room by your own maid, then later she clears and sets up futon beds. You can forget having a nice lay-in in the morning, because shortly before your designated breakfast time she appears again to remove the beds and set the table for breakfast.

The maid at our first ryokan surprised us by speaking in French when she heard us. She spoke French really well, with very little accent. It turned out that she had studied it at university and spent some time there too. It seems that in Japan, working in the hospitality industry is not ill considered at all. In another hotel we were talking to the young lady who led us to our room, who had studied at a university in the US. I don't think you'll find many native university graduates working in hotels in the US or Europe.

It was the crab season, in an area famous for its crabs. We both really like crab, but when every single course of the meal contains it, it becomes a bit overwhelming. We had boiled crab, fried crab, stewed crab, crab soup, cold boiled crab, cold fried crab. And crab sake and crab sashimi - both of which I really don't recommend. About the only thing we didn't have was crab ice cream. Then it was time for bed. There's absolutely nothing to do in most ryokans after dinner, so we ended up asleep by 9.30 every night. At least the futons here were seriously high quality, as comfortable as a bed.

The next day's plan was to explore Kinosaki Onsen. Except that actually there isn't much to explore. The principal feature of an onsen is the variety of public baths. Here there are seven of them, all very different. We decided to start by taking the cable car that goes up the hill to the inevitable temple. By the time we got there, though, it had started to rain seriously. Reluctant to be stranded on a hillside in a downpour, we took refuge in the Dreams Come True Café, opposite the cable car station. This was a very charming place in an extraordinarily Japanese way. It's run by a guy in his 50s, I'd say, who has two fixations: the eponymous Japanese girl band, and his extremely cute tiny dog. When we arrived most of the chairs were taken by a group of elderly Japanese men, whose departure soon afterwards was prompted by the arrival of a minibus to take them... who knows where. For a while we were on our own with just the proprietor and his dog, the latter's life story given in great detail on the back of the menu alongside a potted history of the band.

The downpour got heavier and heavier, the kind of soaking that you rarely see, then there were two lightning strikes within a hundred yards or so of the café. There's nothing quite like a direct hit to get your attention! It was about then that we decided we might as well settle down to lunch. We chose a Japanese interpretation of the french "croque monsieur", a toasted ham and cheese buckwheat pancake, which was very good. We were joined by a party of teenage boys, on their way home from a sports match of some kind. They'd certainly worked up an appetite, given the size of the lunches they demolished with relish.

By now it was time for our next engagement. As we were checking out of our hotel, we were approached by the manager who asked us in a suitably deferential Japanese way whether we'd be prepared to meet a TV crew who were making a program about foreign tourists in Japan. They'd certainly have their work cut out, because in an out of the way place like Kinosaki they were very lucky to find any at all. We chatted with them, and they wanted some footage of us walking to the bath, kitted out in all the obligatory onsen-tourist gear: yukata, happi coat and geta. The latter are wooden sandals, like flip flops but with wooden "teeth" on the soles that give your feet a couple of inches clearance above the ground - handy in the days when streets were deep with mud or worse, but extremely challenging to walk in without either tripping up or having them fall off.

We'd arranged to meet them at the next night's hotel, just across the street from the Nishimuraya. This was a fairly typical ryokan, which is to say much less luxurious, and a lot cheaper! By now the rain had settled down to heavy drizzle, but it was ice cold. The walk to the bath wasn't far, a couple of hundred yards, but hobbling along in geta and a yukata, clutching an umbrella with one hand while desperately trying not to trip, made it seem a lot further. By the time we arrived my hands were frozen, and smiling for the camera - rather than the chilled grimace which came naturally - was not easy. The hot bath was extremely welcome.

We were told that our chilly adventure would be shown on Japanese TV a few days after we left, but we never found out whether we'd really made it to stardom.

Afterwards (and dressed in warm clothes!) we explored the main street. It was lined with tourist souvenir shops of various kinds. Isabelle explored the kimono shops, while I walked to the river. The town is on an estuary and you might suppose that the river, with its view out to the bay, would be one of the sights. But as always the Japanese disdain the water. After negotiating my way through an industrial yard and a parking lot, I came to the neglected, semi-derelict waterfront. The views upriver to the mountains were magnificent, but I was the only one there to appreciate them.

The next morning we were dutiful tourists. We went to another public bath - though dressed normally this time, like all the Japanese visitors we saw. We visited the "barley museum", a curious little place where we did meet another foreign tourist, a Swiss lady who courageously, considering she spoke no Japanese, was visiting these outlying places on her own. The museum is a showcase for local handicraft to decorate boxes and the like with intricate patterns made from scraps of dyed barley. We watched a video showing an old man carefully cutting the barley, gluing it to thin rice paper with rice glue, cutting it again and so on. The rice glue means that all this fine work will be destroyed both by too much humidity and by too little.

Then it was time for our next train journey. A tiny single car diesel from the Kyoto Tango Railway again took us on a lonely single track line along the coast. Sometimes we were in sight of the sea, sometimes passing through tunnels to inland valleys. We saw snow, even though we never got above a few hundred feet. Every couple of miles was a little station where a handful of people got on or off. You pay the driver when you get off, according to prices showing the fare from every station we had been to so far. This is Japan, nobody would cheat. There was an elderly couple in front of us who began their preparations about four stations ahead of theirs. At each stop I thought, "Surely this must be the one?" But no, they stayed there, fiddling around, putting things away, looking at their tickets. They seemed nice enough but it was quite a relief when they finally gave the driver their fare and descended to the platform.

Soon we were at Amanohashidate, after following the bay shore for a couple of stations. There was a minibus waiting to take us to our hotel. We climbed its long, steep driveway, wondering whether we would have to do this on foot every time we returned. But they had a very civilized system - the hotel also owned a coffee shop at the bottom of the hill, on the main road. All we had to do was go into the coffee shop and ask - five minutes later the bus was there to whisk us back to the hotel.

The view from the hotel reception was spectacular, straight out to the sandbank that gives the place its name. Literally it means "bridge to heaven". We hoped that our room would be as good - and in fact it was even better. It was hard not just to stand in the window admiring it, every slight change in the light giving a different impression. The hotel - the Genmyoan - was the height of luxury. Our room was vast, probably twice the size of a typical Japanese apartment for a family. As always we had our own room-maid, a lady I guess in her 50s who talked absolutely incessantly. I could just keep up with her Japanese, luckily it was rarely anything complicated. Our short stay there did wonders for my Japanese conversational fluency! Given that I spoke some Japanese, I don't think it occurred to her that I wasn't fluent. She did understand, though, that Isabelle understood absolutely nothing. Every few sentences she would turn to her and say "I'm sorry, thank you", expending her entire English vocabulary in a single sentence.

 Amanohashidate at sunrise

 Our room at the Genmyoan, complete with Gaijin Chairs

She was very understanding though. She quickly realised that for us, the normal Japanese seated position on a thin cushion on the tatami was not exactly comfortable. She summoned a porter who arrived with two of what we called "gaijin chairs", like normal chairs with arms and a back, raised about a foot off the tatami. What a difference that made to the enjoyment of our meals!

After we'd drunk our ritual cup of tea and extensively admired the view, we took the bus down to the town, Monju. Strictly speaking the name Amanohashidate refers only to the sand bank itself, although the train station is named after it. There are a couple of bridges that cross the ocean channel onto the sand bank and from there you can walk its two mile length to Fuchu, the town on the other side. But that was for the next day. One of the bridges swings open, to allow larger boats to access the sea - fun to watch, especially as there's nothing else to do if you're waiting to cross it.

The town has all the usual tourist attractions: a very pleasant temple, giant shops selling local delicacies and all the rest. You can also rent bicycles, a quicker way to cross the sand bar. It didn't take us long to explore all it had to offer. Somewhere we'd bought some excellent roasted chestnuts, a specialty of the area, which we enjoyed with our tea and coffee while we waited in the hotel's coffee shop for the shuttle to take us back.

Dinner was excellent, the usual ryokan kaiseke meal, this time with rather lass crab - thank goodness. This is not an onsen - a natural hot spring - so the bath was nothing special, though enjoyable. Once dinner is over there is nothing to do but sleep - night life in small Japanese towns, even highly touristic ones, is utterly, totally non-existent. At least the futons were comfortable, as thick as a normal mattress, soft and wider than usual too. A classic futon is thin and just barely wide enough to sleep on, anything but comfortable.

The next morning, after an excellent Japanese breakfast served by our voluble room maid, we set out to walk across the sand bar. It's a very pleasant walk - taken at a slow amble, with frequent pauses to read the life stories of the trees or admire the view out to sea or inland to the bay, it takes about an hour. Every single tree is numbered and logged. Many of them are named, with plaques explaining (only in Japanese of course) the origin of the name and the life story of the tree. They have very shallow roots, necessarily since the surrounding water is salty, so they are very vulnerable to storms. There was a big storm in the 90s which blew down hundreds of trees. One of the biggest has been left as a sorry memorial with (of course) a plaque describing its life story.
 Amanohashidate from the western end
 Kamome, with kamome

At the far end is another small town. It is much more touristic, with many stands selling all kinds of fried and grilled snacks of dubious origin. We bought some more chestnuts, much less good than the previous day's. The main attraction is a funicular which climbs the hill, first to a viewing point for Amanohashidate, and then further to the inevitable temple. We stopped half way, to indulge in the prescribed exercise of standing on a stone and bending double to admire the view from between our legs. Supposedly it's like this that the scenery truly resembles a bridge going skywards to heaven. So they say. Anyway the view is beautiful.

For the journey back we took the ferry. It's called Kamome, which means seagull, and they encourage you to buy bird food on the boat to throw to the gulls, who swoop around catching it as they follow the boat. That explains the cloud of gulls we'd noticed around the boat from our hotel room. If you don't want to wait for the ferry, there are water taxis which will take you for a tour of the sand bar or the bay. It would have been fun, but we didn't really have time.

After an excellent lunch of soba, it was time to catch the next train. At the hotel we all said our goodbyes, our room maid included. There was lots of bowing and "aah, nihongo-wa jouzu desu-nee". That means "your Japanese is really good", but it's used for anyone who can say please and thank you.

Our next stop was in Kyoto. There is a non-stop express train every hour, initially taking the extraordinary Miyafuku Line. The line itself is ordinary enough, a single track winding its way through completely empty countryside for 30 km or so. What's extraordinary is that it was built at all. It was discussed on and off for most of the 20th century, and approved for construction in 1953. But it was only completed in 1988 - by which time the near-bankrupt Japanese National Railway had been closing country railways for two decades, just like everywhere else in the world. Compared to the prior line a little further east, it knocks maybe 20 minutes off the journey time between Kyoto and Amanohashidate. It's a wonderful thing that Japan has such excellent railways, even in the depths of the countryside, but sometimes you wonder why when much more socially valuable lines, as in Hokkaido, have long since been closed.

We had planned all along to stay in a Western style hotel in Kyoto, the Granvia which is an integral part of the station shopping complex. We figured that after three days in traditional ryokan, we'd be grateful for a normal bed and a pizza, which was indeed the case. The lady who took us to our room knew San Francisco well - she'd lived in the US for a while as a student. Once again it struck us that in Japan, hospitality is not considered a low-status profession.

 Contemplative view at Shisen-do
We've been to Kyoto many times, and while it's always a pleasure to visit the well known temples like Kiyomizu-dera and Ginkaku-ji, it's also nice to find a lesser known one. We chose Shisen-do, to the north on the western flank of Higashiyama. It was built as a private residence, the retirement home of Ishikawa Jozen who lived from 1583 to 1672 - not a bad innings for the period. It has a wonderful classical garden, and a room from which you can sit on the tatami and admire it. I could have spent hours just sitting there in contemplation, despite the steady drizzle.

We went there on the bus. One great thing in Japan is the rail card, known as Suica or Pasmo depending on where you buy it. Originally it worked just in Tokyo, but now you can use it on buses and trains throughout the country, and also in convenience stores and such. Much easier than trying to find the exact change in ¥10 pieces.

On the way back to our hotel we stopped at the giant Teramachi indoor shopping arcade. I have memories from our first ever trip together to Kyoto, of buying a set of airport vehicles for my son Joe, who was then about 6. I still have the little orange and white bus on my desk. Now there are only clothes shops, all the toy stands and other lower-margin things have disappeared.

And then... back to Tokyo, 2.5 hours on a packed Shinkansen, and a different room in our favourite hotel.

We decided to get up early and take one last look at the Tsukiji fish market. There have been plans for ever to move this out of central Tokyo to the suburbs, as has happened to many wholesale markets throughout the world. It is finally coming to fruition because the enormous site will be used for the Olympics in Tokyo in 2020, similar to what happened to the Stratford area in London for the 2012 Olympics. They will have to get a move on, though, because for the moment, with only a couple of years to go, it is still a fully functioning fish market.

When I first visited Japan (1982!) and for a while afterwards, Tsukiji was a well kept secret. You could just show up there and stand at the back of the tuna auctions, or wander around the market stalls with their amazing array of different fish. But then it became part of the tourist "must do" list, and the market operators and users understandably got fed up with having the narrow passageways clogged with gawking spectators. Now, there are a handful of designated spectator places at the tuna auction - you have to be there by 3am to get one. The whole market is off-limits if you don't have official business there. We took a taxi, which dropped us at the furthest corner, far away from anything interesting. We suppose the taxi drivers are under orders to do this. Since we knew our way around we were able to find our way to the tuna auction. We peered through the doorway, carefully avoiding the motor carts which zoom around through the narrowest openings, turning on a ¥100 piece and generally making the experience potentially lethal.

We did wander through the halls as before, but only because nobody spotted us. Inevitably we eventually ran into a security guard, who made it very clear that we were to leave by the shortest path, and definitely not pass Go. Not before we passed in front of one stand with just a few pieces of very dark meat and a sign in several languages saying "no photography". We were pretty sure it was selling whale meat - the only one we saw. All the others were perfectly happy to be photographed, as long as you kept out of the way of people earning a living.

Outside the market there are several streets selling associated stuff, like tableware and kitchen equipment. On a visit there a good few years back, we went into one of the sushi bars used by the market workers, where an old man with very few teeth insisted that I share his sake. We didn't find anywhere like that this time, though we did buy several plates and dishes.

For lunch we met our friend Kumiko-san. We were colleagues 10 years ago. Since then she has had two sons, one the same age as my grandson. She lives way outside Tokyo, in  the ski and summer resort town of Karuizawa. This was her first outing in Tokyo since her youngest son was born. We ate at a spectacular sushi restaurant on the 47th floor of the Carettea Shiodome building. There is a magnificent view over the water side of Tokyo, and especially over Tuskiji. It is only seeing it from the air that you can realise just how truly vast it is.

We still had time before our flight. Isabelle had found by chance a tiny shop selling cat-themed... stuff, and she took me there. They have cat mugs, cat calendars, cat notepads, cat sweaters, cat socks... We came away with way too much cat stuff, including the drink mat at the end of this piece.

And then, a taxi to Hamamatsuchou station, and the Tokyo Monorail out to Haneda. As always in Tokyo, things change. The monorail station used to be a dump, with two grubby escalators up the side of the building and cramped, narrow passageways, difficult to navigate with baggage. Suddenly it is almost palatial, like a replica of a Moscow subway station.

Haneda was a delight as always, not even the shortest wait at any point through the airport. And then back home, courtesy of JAL.

## Problem Statement

How big do my hash buckets need to be? What kind of a question is that anyway?

Let's stand back a bit...

As every computer scientist ought to know, a hash table is a wonderfully efficient, O(1), way to look something up in a table. The idea is simple. For each thing you want to look up, you calculate a hash, which is simply a way to scrunch together the bits of its key such that they all get mixed together and any hash value is as likely as any other. The hash should be equal to the number of entries in the table, so you can use it to index to the table. That is where your object should be. Simple.

The complication is that it's possible for two keys to hash to the same value. Classically, there are two ways to deal with this:
• Just go to the next entry, and if that is full, the next one, and so on. This works, but gives disastrous performance if the table gets anywhere close to full. There are techniques for improving this, or at least making it less disastrous, for example quadratic rehash. But it is never good.
• Instead of keeping the actual values in the table, keep a pointer. Then when collisions occur, just chain together the values in a linked list. This works well and doesn't have the performance problems of the first method, but it is seriously cache unfriendly since the chances are that the chained overflow entries won't be in cache, and there is no easy way to prefetch them.
Our system uses a hash table to associate incoming network packets with other packets from the same TCP or UDP session (a flow), using the IP addresses and TCP/UDP ports as a key. This is intense real-time code, intended to handle up to 15 million packets per second. This kind of performance requires attention to the tiniest details. For example, absolutely everything has to be in level one cache before it is accessed.

To achieve this, we use a different scheme to handle hash collisions. Each entry in the table is a fixed size bucket. If two or more flows collide to the same bucket, they are placed in successive slots in the bucket. It's easy to prefetch a whole bucket, so this is cache friendly. As long as the buckets are big enough, this always give excellent performance.

Which brings us back to the first question - how big do the buckets need to be? If there is no free slot in a bucket when a new flow arrives for it, the packets of the flow are simply dropped. So the probability of this happening has to be extremely low, so low that the risk is no higher than for all the other bad things that can happen to a packet in a network.

We could always make the buckets so enormously huge that this just never happens. But there is a cost both in memory and in performance - since a bucket has to be prefetched even if most of it is empty. So we really need to know the optimum size.

So the question can be stated: given a hash table size k, and a number of concurrent flows occupying it, what is the probability that slot b in the bucket will be occupied? In the text that follows  f is the load factor of the table, i.e. n/k.

## Results

The answer to the question is given by the following formula, where f=n/k:
$P(n,k,b) < e^{-f}\cdot \frac{f^{b}}{b!}\frac{b}{b-f}$
This formula involves several approximations, and is a close upper bound on the actual probability.

To know whether a bucket of size b will overflow, we need to know whether the (b+1)th slot will be full, i.e. the first slot beyond the bucket size.

The following table gives the probability of bucket overflow, for various bucket sizes and various load factors. (Some values are not present for small bucket sizes because the above approximation is not applicable when the load factor is greater than the bucket size).

 Load 0.1 0.5 1 1.5 2 Bucket Size 1 0.0050269 0.1516327 2 0.0001587 0.0168481 0.1226265 0.5020429 3 0.0000039 0.0018954 0.0229925 0.0941330 0.2706706 4 0.0000001 0.0001805 0.0040875 0.0225919 0.0721788 5 0.0000000 0.0000146 0.0006387 0.0050428 0.0200497 6 0.0000000 0.0000010 0.0000876 0.0010086 0.0051556 7 0.0000000 0.0000001 0.0000106 0.0001805 0.0012030 8 0.0000000 0.0000000 0.0000012 0.0000291 0.0002546 9 0.0000000 0.0000000 0.0000001 0.0000043 0.0000491 10 0.0000000 0.0000000 0.0000000 0.0000006 0.0000087 11 0.0000000 0.0000000 0.0000000 0.0000001 0.0000014 12 0.0000000 0.0000000 0.0000000 0.0000000 0.0000002

These probabilities are independent of table size. But the probability of a at least one bucket being of this size depends on the table size as well. So for example, in a filled table of 10,000 entries and bucket size of 7, there is a probability of about 0.1 that a bucket will overflow (i.e. need to be size 8 or greater), which is probably acceptable. But if the table size is increased to 1,000,000, that probability increases to practically 1. To achieve the same 0.1 probability as for the smaller table, the bucket size must be increased to 9.

To be precise, the probability that at least one bucket in a table of size k, having n entries and a bucket size of b, will overflow, is given by:
$p_{overflow}(n,k,b))=1-(1-p(n,k,b))^{k}$ The following table shows the probability of at least one bucket becoming full, for the given table and bucket sizes, at a load factor of 1 (i.e. n=k).

 Table Size 1000 10000 100000 1e+06 1e+07 2 1 1 1 1 1 3 1 1 1 1 1 4 0.98336 1 1 1 1 5 0.472119 0.99832 1 1 1 6 0.083867 0.58353 0.999843 1 1 7 0.010588 0.100977 0.65509 0.999976 1 8 0.001158 0.011519 0.1094 0.686076 0.999991 9 0.000114 0.00114 0.01134 0.107787 0.680341 10 1e-05 0.000102 0.001023 0.010188 0.097333 11 1e-06 8e-06 8.4e-05 0.000844 0.008413 12 0 1e-06 6e-06 6.4e-05 0.000644

## Derivation: Some Basics

There's a well known analysis concerning the number of empty buckets you can expect to find in a hash table. Considering a single bucket, we ask: what is the probability that not a single entry will have hit it? This is the same as asking whether every entry has hit somewhere else. For  single entry, this is (k-1)/k, so for every entry to have hit somewhere else, the probability is:
$p(n,k,0)=\left ( \frac{k-1}{k} \right )^{n}$
We'll use the notation p(n,k,b) to mean the probability that a bucket in a table of size k with n entries has exactly b slots used - in this case, b is zero. With a bit of approximation, this can be simplified to:
$p(n,k,0)= e^{-f}$
In particular, for a table where n=k, i.e. f=1, this is 1/e, or about 0.368. So in a table of size 1,000,000, with that many entries, about 368,000 will be empty. The rest will have at least one entry. How many will have more than one?

We can consider the probability of a single key finding itself alone in a single bucket. This is the probability that it will go the bucket, 1/k, times the probability that nobody else will, which is ((k‑1)/k)n-1. Now we have to consider that for every single entry, so we multiply it by n. This gives:
$p(n,k,1)=\left ( \frac{k-1}{k} \right )^{n-1}\cdot \frac{1}{k} \cdot n$
which can be simplified, with a little approximation, to:
$p(n,k,1)= f e^{-f}$
For the particular case of n=k, this gives exactly the same result as for an empty bucket: 0.368.

## The Equation We're Looking For

All we need to do now is to generalise the above result for a single entry, to cover b entries. We use the same logic: consider any b specific keys, what is the probability that they will end up together and with no other keys, in a given bucket? The probability that no other keys will be there is ((k‑1)/k)n-b, while the probability that they will all end up in this particular bucket is k-b. Then we need to multiply this by the number of combinations of b keys, which is given by nCb. Putting this all together gives:
$p(n,k,b)=\left ( \frac{k-1}{k} \right )^{k-b}\cdot k^{-b}\cdot \binom{n}{b}$
This can be simplified, again with a little approximation, to:
$p(n,k,b) = e^{-f}\cdot \frac{f^{b}}{b!}$
This tells us the probability that a bucket will have exactly b entries. What we need, though, is the probability that it will have b or more entries. Calling this function P, we have:
$P(n,k,b)=\sum_{i=b}^{\infty}p(n,k,b)=\sum_{i=b}^{\infty}e^{-f}\cdot \frac{f^{b}}{b!}$
There is no closed form for this sum, but there is a good upper bound:
$P(n,k,b) < e^{-f}\cdot \frac{f^{b}}{b!}\frac{b}{b-f}$

## The Math: Obtaining the Simplified Formulae

First, recall that by the definition of e:
$e^{x}=\lim_{k\rightarrow \infty }\left ( 1+\frac{1}{k} \right )^{xk}$
Hence, substituting -k for k, and considering that k is close enough to infinity:
$\left ( \frac{k-1}{k} \right )^{n}=\left ( 1-\frac{1}{k} \right )^{k\cdot \frac{n}{k}}=\left ( 1+\frac{1}{k} \right )^{-k\cdot \frac{n}{k}}\simeq e^{-f}$
Now consider the equation for b=1:
$p(n,k,1)=\left ( \frac{k-1}{k} \right )^{n-1}\cdot \frac{1}{k}\cdot n$
We rearrange things to get the same approximation for e-f, and observe that since k is large, (k-1)/k is approximately 1. And so:
$\left ( \frac{k-1}{k} \right )^{n-1}\cdot \frac{1}{k}\cdot n\simeq \left ( \frac{k-1}{k} \right )^{n}\cdot \left ( \frac{k-1}{k} \right )^{-1}\cdot \frac{n}{k} \simeq f e^{-f}$
For the general case, b>1:
$p(n,k,b)=\left ( \frac{k-1}{k} \right )^{k-b}\cdot k^{-b}\cdot \binom{n}{b}$
we consider first the combinatorial term on the right. Since n»b, we can treat the product in the denominator as nb:
$\binom{n}{b}=\frac{n!}{(n-b)!b!}=\frac{n(n-1)\ldots (n-b+1)}{b!}\simeq \frac{n^{b}}{b!}$
Incorporating this approximation and noting as before that k-1/k can be treated as 1, and that n/k is the same as f:
$\left ( \frac{k-1}{k} \right )^{n-b}\cdot k^{-b}\cdot \binom{n}{b}\simeq \left ( \frac{k-1}{k} \right )^{n}\cdot \left ( \frac{k-1}{k} \right )^{-b}\cdot k^{-b}\cdot \frac{n^{b}}{b!} \simeq e^{-f}\cdot \frac{f^{b}}{b!}$
Considering now the required value that all slots higher than b are empty, this is given by:
$P(n,k,b)=\sum_{i=b}^{\infty}p(n,k,b)=\sum_{i=b}^{\infty}e^{-f}\cdot \frac{f^{i}}{i!}=e^{-f}\cdot\sum_{i=b}^{\infty}\frac{f^{i}}{i!}$
There is no closed form for such a sum. But we can obtain an upper bound by considering the value of the term in i as ti:
$t_{i}=t_{i-1}\cdot \frac{f}{i}<t_{i-1}\cdot \frac{f}{b}\:\:\:\:\text{(since }\textit{b}<\textit{i}\text{)}$ Hence by induction: $t_{i}<\frac{f^b}{b!}\cdot\frac{f^{i-b}}{b^{i-b}}$ And hence: $P(n,k,b)<e^{-f}\frac{f^b}{b!}\sum_{i=0}^{\infty}\frac{f^{i}}{b^{i}}$ And so by the usual formula for an infinite geometric progression: $P(n,k,b)<e^{-f}\cdot\frac{f^b}{b!}\cdot\frac{1}{1-\frac{f}{b}}=e^{-f}\cdot\frac{f^b}{b!}\cdot\frac{b}{b-f}$